Problem Description
F(x,m) 代表一个全是由数字x组成的m位数字。请计算，以下式子是否成立：
F(x,m) mod k ≡ c
F(x,m) mod k ≡ c
Input
第一行一个整数T，表示T组数据。
每组测试数据占一行，包含四个数字x,m,k,c
1≤x≤9
1≤m≤1010
0≤c<k≤10,000
每组测试数据占一行，包含四个数字x,m,k,c
1≤x≤9
1≤m≤1010
0≤c<k≤10,000
Output
对于每组数据，输出两行：
第一行输出："Case #i:"。i代表第i组测试数据。
第二行输出“Yes” 或者 “No”，代表四个数字，是否能够满足题目中给的公式。
第一行输出："Case #i:"。i代表第i组测试数据。
第二行输出“Yes” 或者 “No”，代表四个数字，是否能够满足题目中给的公式。
Sample Input
3
1 3 5 2
1 3 5 1
3 5 99 69
Sample Output
Case #1:
No
Case #2:
Yes
Case #3:
Yes
All X
Hint
对于第一组测试数据：111 mod 5 = 1，公式不成立，所以答案是”No”，而第二组测试数据中满足如上公式，所以答案是 “Yes”。思路：
注意到：xx……x = x*（10^m-1）/ 9；
因此 c = （xx……x）%k；
（c * 9）%k = （x*(10^m) - x）%k；
（c*9 + x）%k = （x*(10^m)）%k；
用快速幂求得10^m ;
验证上式是否正确即可。
代码：
1 #include<cstdio> 2 #include<iostream> 3 using namespace std; 4 typedef long long LL; 5 6 LL PowerMod(LL a,LL b,LL c) 7 { 8 LL ans=1; 9 a=a%c; 10 while(b>0) 11 { 12 if(b%2==1) 13 ans=(ans*a)%c; 14 b=b/2; 15 a=(a*a)%c; 16 } 17 return ans; 18 } 19 20 int main() 21 { 22 LL cas=1,t; 23 LL m,x,c,k; 24 scanf("%lld",&t); 25 while(t--) 26 { 27 scanf("%lld%lld%lld%lld",&x,&m,&k,&c); 28 LL p=PowerMod(10,m,k); 29 if(x*p%k==(9*c+x)%k) /// xx……x = x*(m-1)/9 30 printf("Case #%lld: Yes ",cas++); 31 else 32 printf("Case #%lld: No ",cas++); 33 } 34 return 0; 35 }