HDU 5690:2016"百度之星" - 初赛 All X

原文链接: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”,代表四个数字,是否能够满足题目中给的公式。
 
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
Hint
对于第一组测试数据: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;
}

上一篇:QT开发应用程序的欢迎界面


下一篇:JVM 调优总结