联通数

问题描述

数学高手小G最近发现了一种新型的数！
他首先在草稿纸写下任意长度的数字串kkkkkkkkkkk...(1≤k≤9)并在其中间添加加号，且相邻两个加号之间至少含有两个数字k (默认数字串第一个数字前与最后一个数字后也有两个加号)，然后对其进行求和得出一个新的数。像这样得出的数他将其定义为 “k联通数 ”。
小G对于他的发现感到非常的自豪，像数字854就能表示为77+777，因此854是7联通数。
小G现在非常好奇，究竟有哪些数可以是k联通数呢？他想考验一下你。
询问T次，每次给定两个数n,k，判断n是否为k联通数，如果是，输出YES，否则出NO。

输入格式

第一行一个整数T，表示询问个数。
接下来T行，每行两个整数n,k，意义如上所示

输出格式

T行，每行输出 YES 或 NO。

样例输入

854 7

111 2

554 2

样例输出

YES

数据范围

题解

观察题目给的例子 854=77+777=7*(11+111)

事实上对于任意一个k联通数，可以写成如下形式：

n=k×(num₁*11+num₂*111+num₃*1111+……) ，其中num_i为非负整数

显然若n不是k的倍数，则n一定不是k联通数

若n为k的倍数，则问题转化为判断n/k是否由num₁*11+num₂*111+num₃*1111+……组成

探究11,111,1111，……这些数的关系

11=11

111=111

1111=11*100+11

11111=111*100+11

111111=111*1000+111

1111111=111*10000+11*100+11

……

我们发现，所有11,111,1111，……这些数都可以拆成111*x+11*y的形式（x，y为非负整数）

对于n/k,我们枚举x，再判断是否存在y，使得111*x+11*y==n/k即可

即判断n/k-111*x是否为11的倍数

 1 #include <cstdio>
 2 #define ll long long
 3 int T,k;
 4 ll n,x;
 5 int main()
 6 {
 7     int i;
 8     bool flg;
 9     scanf("%d",&T);
10     while (T--)
11     {
12         scanf("%lld%d",&n,&k);
13         if (!n || n%k)
14         {
15             printf("NO
");
16             continue;
17         }
18         x=n/k;
19         for (i=flg=0;i*111ll<=x;i++)
20           if (!((x-i*111ll)%11))
21           {
22               flg=1;
23               break;
24           }
25         if (flg) printf("YES
");
26         else printf("NO
");
27     }
28     return 0;
29 }