原文链接:https://www.dreamwings.cn/hdu5690/2657.html
All X
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 703 Accepted Submission(s): 328
Problem Description
代表一个全是由数字组成的位数字。请计算,以下式子是否成立:
Input
第一行一个整数,表示组数据。
每组测试数据占一行,包含四个数字
每组测试数据占一行,包含四个数字
Output
对于每组数据,输出两行:
第一行输出:"Case #i:"。代表第组测试数据。
第二行输出“Yes” 或者 “No”,代表四个数字,是否能够满足题目中给的公式。
第一行输出:"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: YesHint对于第一组测试数据:111 mod 5 = 1,公式不成立,所以答案是”No”,而第二组测试数据中满足如上公式,所以答案是 “Yes”。
Source
一般输出只有Yes或者No的题目都是有规律的~学长说的,然后一般测试数据过了提交总是wrong answer!
一个由x组成的m位数也可以表示成(10^m-1)*x/9对吧!
既然这样,只需要证明((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; }