All X

Accepts: 1281

Submissions: 7580

Time Limit: 2000/1000 MS (Java/Others)

Memory Limit: 65536/65536 K (Java/Others)

Problem Description

F(x, m)F(x,m) 代表一个全是由数字xx组成的mm位数字。请计算，以下式子是否成立：

F(x,m)\ mod\ k\ \equiv \ cF(x,m) mod k ≡ c

Input

第一行一个整数TT，表示TT组数据。每组测试数据占一行，包含四个数字x,m,k,cx,m,k,c

1\leq x\leq 91≤x≤9

1\leq m\leq 10^{10}1≤m≤1010

0\leq c< k\leq 10,0000≤c<k≤10,000

Output

对于每组数据，输出两行：第一行输出："Case #i:"。ii代表第ii组测试数据。第二行输出“Yes” 或者 “No”，代表四个数字，是否能够满足题目中给的公式。

Sample Input

Sample Output

Case #1:

No

Case #2:

Yes

Case #3:

Yes

Hint

对于第一组测试数据：111 mod 5 = 1，公式不成立，所以答案是”No”，而第二组测试数据中满足如上公式，所以答案是 “Yes”。

思路：这题可以用矩阵快速幂，可推同模公式，貌似还有求循环节什么的，我用的是第二种。如下：

m个x模k为c，则 x *(10 ^ m - 1)/ 9 %k = c

则x *(10 ^ m - 1) % (9 * k) = 9*c %(9 * k)

用矩阵的话用此矩阵快速幂(赛后学的)

代码如下：

#include<iostream>

#include<cstdio>

#include<string>

#include<cstring>

#include<cstdlib>

#include<queue>

#include<vector>

#include<algorithm>

using namespace std;

typedef long long LL;

LL PowMod(LL a,LL b,LL MOD){

    LL ret=;

    while(b){

        if(b&) ret=(ret*a)%MOD;

        a=(a*a)%MOD;

        b>>=;

    }

    return ret;

}

int main(){

    LL x, m , k, c;

    int t;

    cin>>t;

    for(int i = ; i <= t; i++){

        scanf("%I64d %I64d %I64d %I64d", &x, &m, &k, &c);

        k *= ;

        LL a = ((PowMod(, m, k) + k - ) % k) * x %k;

        LL b = ( *c) % k;

        printf("Case #%d:\n",i);

        if(a == b){

            printf("Yes\n");

        }else{

            printf("No\n");

        }

    }

    return ;

}

巴特西

2016"百度之星" - 初赛（Astar Round2A）All X(数学矩阵)

All X

最新文章

热门文章

巴特西

2016"百度之星" - 初赛（Astar Round2A）All X(数学 矩阵)

All X

最新文章

热门文章

2016"百度之星" - 初赛（Astar Round2A）All X(数学矩阵)