HDU 5690：2016

HDU 5690：2016

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

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

Hint

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 #include 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;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。