1 条题解

  • 2
    @ 2022-10-29 21:35:20

    会发现,1111 = 11 ∗ 101 , 11111 = 11 + 111 *100 . . . 即这些数都能表示为 11 和111的组合。因此若 x 可以表示为 11a+111b(0≤a,b),则可以拆分,反之不行

    继续推导:

    11a+111b=11(a+10b)+b=x

    b≡x(mod11)

    a+10b=xb11\frac{x-b}{11}

    a=xb11 \frac{x-b}{11} −10b≥0

    b最小为x%11 ,因此 x11\lfloor \frac{x}{11} \rfloor− 10 ( x % 11 ) ≥ 0则有解,反之不行。

    #include <bits/stdc++.h>
    using namespace std;
    int main()
    {
        int t;
        scanf("%d", &t);
        while (t--)
        {
            int n;
            scanf("%d", &n);
            int ans = n / 11;
            int cnt = n % 11;
            if (cnt * 10 <= ans)
            {
                printf("YES\n");
            }
            else
            {
                printf("NO\n");
            }
        }
        return 0;
    }
    
    • @ 2022-10-31 17:28:30

      关于b的最小值为什么是x%11,证明如下:

      因为x和b模11同余,所以b%11=x%11, 则b可以写为11*k+x%11,当k为0时,b最小,也就是x%11

信息

ID
825
时间
1000ms
内存
256MiB
难度
9
标签
递交数
404
已通过
38
上传者