Problem Description
F(x,m) 代表一个全是由数字x组成的m位数字。请计算，以下式子是否成立：
F(x,m) mod k ≡ c
Input
第一行一个整数T，表示T组数据。 每组测试数据占一行，包含四个数字x,m,k,c
1≤x≤9
1≤m≤10^10
0≤c<k≤10,000
Output
对于每组数据，输出两行： 第一行输出："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
Hint
对于第一组测试数据：111 mod 5 = 1，公式不成立，所以答案是”No”，而第二组测试数据中满足如上公式，所以答案是 “Yes”。
//xxxxxxx|xx*xx%k == c
//因为k<=10000,所以余数范围在[0,10000)内,故定义f[10000](作标记用)
//因为无法用m位的x直接对k取余,考虑周期性,令t=0,不断做运算t=(t*10+x)%k,f[t]=r(数组f初始化为0),
//至第r(至多10001)次时(这实际上和r位的x对k取余的结果相等),一定会出现重复的值,
//此时,r-f[t]即为周期T,也就是说,我们再向前取T位x,对k取余结果依然是t,所以我们只需再向前做(m-f[t])%T
//次(t*10+x)%k运算,从而大大降低运行时间
#include <stdio.h>
#define ll long long
int OK(int x,ll m,int k,int c)
{
int f[] = {},r,t=,left;
for(r=;r<=m;r++)
{
t = (*t+x)%k;
if(f[t])
{
left = (int)((m-f[t])%(r-f[t]));
while(left--)
{
t = (*t+x)%k;
}
return t == c;
}
f[t] = r;
}
return t == c;//m必然小于10001
}
int main()
{
int T,x,k,c,i=;
ll m;
scanf("%d",&T);
while(T--)
{
scanf("%d%lld%d%d",&x,&m,&k,&c);
printf("Case #%d\n",i++);
puts(OK(x,m,k,c)? "Yes" : "No");
}
return ;
}
//1 5 5 1 Yes
//1 3 5 2 No
//1 3 5 1 Yes
//3 5 99 69 Yes
// 8 10000000000 32 14 No
//7 9999998777 24 17 Yes