All X

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)

Total Submission(s): 1002    Accepted Submission(s): 478

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≤1010

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”。

 

 

Source

 

m位x组成的数字可以写成 [(10^m-1)/9*x]%k== c  --> [x*(10^m-1)]%(9*k)== 9*c?; 

 

#include 
      
       #include 
       
        typedef long long LL;using namespace std;LL x, m, k, c;LL deal(LL s, LL b, LL mod){    LL ret= 1;    while(b){        if(b&1) ret= ret*s%mod;        s=s*s%mod;        b>>=1;    }    return ret;} int main(){    int t;    scanf("%d", &t);    for(int i=1; i<= t; i++)    {        scanf("%lld%lld%lld%lld", &x, &m, &k, &c);        LL mod= 9*k;        LL p= deal(10, m, mod);        printf("Case #%d:\n", i);        if(p*x%mod-x%mod== 9*c) puts("Yes");        else puts("No");    }    return 0;}