首页 > 编程学习 > CF1526B I Hate 1111--数学性质推不出来?打表就好啦

题意:

给定一个n,他是否能被 11,111,1111,.......这样的数表示呢

样例:33=3*11,144=111+11*3

解:

首先可以发现的是:1111=1100+11=11*101,11111=11100+11=111*10+11,后面的不难验证都可以由11,111表示

问题缩小了,也就是n能不能被11,111表示

也就是解方程:11x+111y=n,有非负整数解

首先由于gcd(11,111)=1,此方程一定有解,但不一定是非负解

结论是:当不定方程:ax+by=n,gcd(a,b)=1,且n>ab-a-b时,有非负解

也就是当n>11*111-11-111=1099时,都可以被表示

但比赛时想不到怎么办?我的评价是:打表。

可以发现,从n=1100开始,以后的数都可以被表示。大胆猜测n>=1100不用判断

此时,只需要暴力求解n<1100的所有n是否被表示即可

这个范围是非常小的。

#include<iostream>
#include<cstring>
using namespace std;
typedef long long ll;
const int maxn = 0x3f3f3f;
ll f[maxn];
int main()
{
    for (ll x = 0; x <= 100; x++)
    {
        for (ll y = 0; y <= 100; y++)
        {
            ll ans = 11 * x + 111 * y;
            if(ans<maxn)f[ans] = 1;
        }
    }
    int t; cin >> t;
    while(t--)
    {
        int n; cin >> n;
        if (n >= 1100) { cout << "YES\n"; continue; }
        else
        {
            if (f[n])cout << "YES\n";
            else cout << "NO\n";
        }
    }
    return 0;
}

 

Copyright © 2010-2022 mfbz.cn 版权所有 |关于我们| 联系方式|豫ICP备15888888号