CF1526B I Hate 1111 题解

· · 题解

原题传送门

解题思路：

首先讨论由多个 1 组成的多位数与 11 和 111 的关系：

11 = 11 111 = 111 1111 = 11 \times 101 = 11 \times 10^2 + 11 11111 = 11 \times 10^3 + 111 111111 = 11 \times 10101 = 11 \times 10^3 + 1111

综上，容易发现对于各位数字均为 1 的 p 位数（4 \le p），都可以表示为 11 \times 10^{p-2} + \dfrac{10^{p-1}-1}{9}，即 11 \times 10^{p-2}+ 由 p-2 个 1 组成的多位数。而 p-2 个 1 又可以如此分拆，循环下去 ...... 最终能够发现，对于所有 4 \leq p 的 p 位数都可以表示为：11 \times a + 111 \times b，又易得 111 = 11 \times 10 + 1，所以又可以转化为 11 \times (a + 10b) + 1 于是我们只要对输入的数让其对 11 取模，得到的余数 f 表示其必有 f 个 111。所以只需要判断输入的数对 11 进行取模后的余数乘上 f 是否小于等于原数即可。

参考代码：

#include <iostream>
using namespace std;

inline void quick_cppio(void)
{
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int main()
{
    quick_cppio();

    int t;
    cin >> t;
    ++t;
    while(--t)
    {
        int x;
        cin >> x;
        int f = x % 11;
        f * 111 <= x ? cout << "YES" << endl : cout << "NO" << endl ;
    }
    return 0;
}

AC 记录