HDU-5690: All X（同余模运算）

数论

Description

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

Input

第一行一个整数，表示组数据。
每组测试数据占一行，包含四个数字 $x,m,k,c$
$1≤x≤9$
$1≤m≤10^{10}$
$0≤c＜k≤10,000$

Output

对于每组数据，输出两行：
第一行输出："Case #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

分析：$≡$ 表示同余，同余：两个整数a、b，若它们除以整数m所得的余数相等，则称a与b对于模m同余或a同余于b模m。
全是由数字x组成的m位数，如果直接循环求该数，由于m是$10^{10}$，那么会超时，因此我们把它表示为$(10^m-1)/9*x$，用快速幂求$10^m$。判断 $(10^m-1)*x$%$k$ 是否等于 $9*c$%$k$ 即可（等式两边同时乘了9）。

• 完整代码：

#include<stdio.h>
#define LL long long
LL quick(LL x,LL m,LL n)
{
    LL ans=1;
    while(m>0)
    {
        if(m%2==1)
            ans=ans*x%n;
        x=x*x%n;
        m=m/2;
    }
    return ans;
}
int main()
{
    int i,t,tt=0;
    LL x,m,k,c,s;
    scanf("%d",&t);
    while(t--)
    {
        tt++;
        scanf("%lld%lld%lld%lld",&x,&m,&k,&c);
        s=quick(10,m,k);        //(10^m-1)/9*x，先求10^m%k
        s*=x;       //求x*10^m%k
        s=(s-x%k+k)%k;      //(x*10^m%k-x%k)%k，x%k+k是为了防止小于0
        printf("Case #%d:\n",tt);
        if(s==(9*c)%k)
            printf("Yes\n");
        else
            printf("No\n");
    }
    return 0;
}