全x数字

contest8-T2

题目描述

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

F(x,m) mod k ≡ c

输入

第一行一个整数T，表示T组数据。每组测试数据占一行，包含四个数字x,m,k,c

输出

对于每组数据，输出两行： 第一行输出："Case #i:"。i代表第i组测试数据。 第二行输出“Yes” 或者 “No”，代表四个数字，是否能够满足题目中给的公式。

样例输入

3
1 3 5 2
1 3 5 1
3 5 99 69

样例输出

Case #1:
No
Case #2:
Yes
Case #3:
Yes

提示

对于第一组测试数据：111 mod 5 = 1，公式不成立，所以答案是”No”，而第二组测试数据中满足如上公式，所以答案是 “Yes”。

1<=x<=9   1<=m<=10^10    0<=c

百度之星初赛的原题，当时没啥思路，没想到考试的时候一下子就想出来了

一个m位的全x数字就是(10^0+10^1+10^2+10^3....+10^(m-1))*x

10^0加到10^(m-1)可以用快速幂求和解决

判断是否模k=c即可

#include 
#include 
#include 
#define ll long long 
using namespace std; 
int cas; 
ll x,m,mod,c,ans; 
ll mi[105],sum[105]; 
ll quick(ll k,int d) 
{ if(k==1) return 10; if(mi[d]!=-1) return mi[d]; ll s=(quick(k/2,d+1)*quick(k/2,d+1))%mod; if(k%2==1) s=(s*10)%mod; return mi[d]=s; 
} 
ll solve(ll k,int d) 
{ if(k==1) return 10; if(sum[d]!=-1) return sum[d]; ll s=((solve(k/2,d+1)*quick(k/2,d+1))%mod+solve(k/2,d+1))%mod; if(k%2==1) s=(s+quick(k,d))%mod; return sum[d]=s; 
} 
int main() 
{ cin>>cas; for(int i=1;i<=cas;i++)  { memset(sum,-1,sizeof(sum)); memset(mi,-1,sizeof(mi)); scanf("%lld%lld%lld%lld",&x,&m,&mod,&c); m--; ans=solve(m,1)+1; ans=(ans*x)%mod; printf("Case #%d:\n",i); if(ans%mod==c) printf("Yes\n");else printf("No\n"); } return 0; 
} 

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！