HDU 5690 All X

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

Hint

解法很多，可以矩陣可以循環節，可以快速幂，随便搞。

#include<map>
#include<set>
#include<queue>
#include<stack>
#include<cmath>
#include<cstdio>
#include<bitset>
#include<string>
#include<vector>
#include<cstring>
#include<iostream>
#include<algorithm>
#include<functional>
using namespace std;
typedef long long LL;
const int low(int x) { return x&-x; }
const int INF = 0x7FFFFFFF;
const int mod = 1e9 + 7;
const int maxn = 1e5 + 10;
int T, cas = 0;
LL x, m, c, k, ans;

int get(LL x)
{
    int res = 1;
    for (int i = 10; x; x >>= 1)
    {
        if (x & 1) res = res*i % c;
        i = i*i%c;
    }
    return res;
}

int main()
{
    scanf("%d", &T);
    while (T--)
    {
        scanf("%I64d%I64d%I64d%I64d", &x, &m, &c, &k);
        ans = 0;
        for (LL i = 1, j = x, k = 1; m; i <<= 1)
        {
            if (m&i)
            {
                (ans += j*k%c) %= c;
                m ^= i; k = k*get(i) % c;
            }
            j = (j + j*get(i)) % c;
        }
        printf("Case #%d:\n%s\n", ++cas, ans == k ? "Yes" : "No");
    }
    return 0;
}