hdu5690(快速幂||减半)All X

2017年08月03日 9点热度 0人点赞 0条评论

All X

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 2165    Accepted Submission(s): 912


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

F(x,m) mod k  c

 


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

1x9 

1m1010

0c<k10,000

 


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
思路1:公式:(10^m−1)×x(mod9k)==9c

#include
#include
#define ll long long
using namespace std;
ll pow(ll a,ll b,ll c)
{
	ll ans=1;
	while(b)
	{
		if(b&1) ans=(ans*a)%c;
		a=(a*a)%c;
		b>>=1;
	}
	return ans;
}
bool solve(ll x,ll m,ll k,ll c)
{
	k=9*k,c=9*c;
	ll ans=pow(10,m,k);
	ans=(ans-1+k)%k;
	ans=(ans*x)%k;
	return ans==c;
}
int main(){
	int T,kase=0;
	ll x,m,k,c;
	scanf("%d",&T);
	while(T--)
	{
		scanf("%lld%lld%lld%lld",&x,&m,&k,&c);
		printf("Case #%d:n%sn",++kase,solve(x,m,k,c)?"Yes":"No");
	}
	return 0;
}

思路2:因为k小于10000,所以可以找个循环节

思路3:拆半,感觉和找循环节有点像,但是更加巧妙

#include
#include
#define ll long long
using namespace std;
bool solve(ll x,ll m,ll k,ll c)
{
	ll t1=0,t2=1,ans=0;
	for(int i=0;i<10000;++i)
	{
		t1=(t1*10+x)%k;
		t2=t2*10%k;
	}
	for(int i=0;i
未经允许不得转载!hdu5690(快速幂||减半)All X

update

纸上得来终觉浅, 绝知此事须躬行。