HDU 5690 2016″百度之星” – 初赛 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

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

思路

一般输出只有 Yes 或者 No 的题目都是有规律的~ 学长说的，然后一般测试数据过了提交总是 Wrong Answer！

一个由 x 组成的 m 位数也可以表示成 $\frac{(10^m-1)×x}9$ 对吧！

既然这样，只需要证明 $\frac{(10^m-1)×x}9\%k==c$ 成立就可以了！

可以把这个式子变换一下，就是 $(10^m\%(9×k)×x)\%(9×k)-x==9×c$

然后秒 A ！

AC 代码

#include <iostream>
#include <stdio.h>
typedef long long LL;
using namespace std;
LL modexp(LL a,LL b,LL n)
{
    LL ret=1;
    LL tmp=a;
    while(b)
    {
       //基数存在
       if(b&0x1) ret=ret*tmp%n;
       tmp=tmp*tmp%n;
       b>>=1;
    }
    return ret;
}
int main()
{
    //printf("%d\n",modexp(3,2,5));
    int N;
    cin>>N;
    for(int i=1;i<=N;i++)
    {
        LL x,m,k,c;
        cin>>x>>m>>k>>c;
        LL mo=9*k;
        LL a=(modexp(10,m,mo)*x)%mo-x;
        printf("Case #%d:\n",i);
        if(a==9*c)printf("Yes\n");
        else printf("No\n");
    }
    return 0;
}