Fair Numbers CodeForces - 1465B

Fair Numbers CodeForces - 1465B

我们定义一个好数规则如下： 它能够整除自己的每一个非零位。
例如说，102 是一个好数，因为它能整除 1 和 2。282 则不是，因为它不能整除 8。
现在给定一个正整数 n，求大于等于 n 的最小好数。

Input

第一行为样例数t(1<=t<=1000)，接下来t行包括一个n(1 <= n <= 1e18)

Output

输出t行，代表大于等于 n 的最小好数。

Sample Input

4
1
282
1234567890
1000000000000000000

Sample Output

1
288
1234568040
1000000000000000000

分析

直接从 n 开始枚举答案即可，其实我本来以为会超时的，毕竟 1e18的范围，但是没有超时，确实有一定的赌博成份在里面。
这个地方记录一下，我觉得需要证明一下这样不会超时。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=1e6+10,INF=0x3f3f3f3f;
LL t,n;
bool chk(LL x) {
    LL m=0, temp=x, a[20];
    while(temp) {
        if(temp%10!=0) a[++m] = temp%10;
        temp/=10;
    }
    int i=1;
    while(i<=m) {
        if(n%a[i]!=0) break;
        i++;
    }
    return i==m+1;
}
int main() {
//    freopen("data.in", "r", stdin);
    cin>>t;
    while(t--) {
        cin>>n;
        while(1) { // TLE ?
            if(chk(n)) break;
            n++;
        }
        cout<<n<<endl;
    }
    return 0;
}