TZOJ 5291 游戏之合成(快速幂快速乘)

描述

zzx和city在玩一款小游戏的时候,游戏中有一个宝石合成的功能,需要m个宝石才可以合成下一级的宝石(例如需要m个1级宝石才能合成2级宝石)。

这时候zzx问city说“我要合成A级宝石需要多少个B级的宝石(A>B)。”

city说:“这数字会好大的。”

zzx:“没事的,你选择一个数取余数就行了,你只要告诉我余数就好了”

city:“那就对梅森素数取余好了”

但最后,由于数字过于大,city又不想手算了,于是想请你帮忙。

输入

多组数据,输入到文件结束为止

每组输入4个正数m,A,B,K,m,A,B为题目描述的意思,K为对第K个梅森素数取余

数据保证M,A,B不会大于第K个梅森素数(K<10)

输出

一个整数为合成A级宝石需要多少个B级的宝石对第K个梅森素数取余的结果

样例输入

5 5 1 2
4 4 1 2

样例输出

2
1

提示

1.第一组样例解释:合成5级宝石需要5个4级的宝石,合成5个4级宝石需要25个3级宝石,以此类推,合成5级宝石需要625颗1级宝石,第2个梅森素数为7,625除7余2.

2.输入输出数据过于庞大,c++输入输出你应该使用scanf和printf,而不是cin和cout

3.梅森素数是由梅森数而来。所谓梅森数,是指形如2p-1的一类数,其中指数p是素数,常记为Mp 。如果梅森数是素数,就称为梅森素数。

梅森素数表

序号

p

Mp=(2p)-1

Mn的位数

发现时间

发现者

1

2

3

1

古代

古人

2

3

7

1

古代

3

5

31

2

古代

古人

4

7

127

3

古代

古人

5

13

8191

4

1456

无名氏

6

17

131071

6

1588

Cataldi

7

19

524287

6

1588

Cataldi

8

31

2147483647

10

1772

欧拉

9

61

2305843009213693951

19

1883

Pervushin

10

89

618970019642690137449562111

27

1911

Powers

题意

输出合成A级宝石需要多少个B级的宝石对第K个梅森素数取余后的值

题解

典型的快速乘+快速幂m^(A-B)%f[k],f[k]代表第k个梅森素数

这题当时是比赛的时候做的题,不会存第9个梅森素数所以没做出来

这个题有3个坑:

1.存第9个梅森素数(2305843009213693951LL)

2.m^(A-B)其中A-B太大会超时(快速幂)

3.第9个素数相乘超过19位爆int64(快速乘)

代码

 #include<stdio.h>
__int64 multi(__int64 m,__int64 n,__int64 mod){
__int64 ans=;
while(n){
if(n&)ans+=m;
m=(m+m)%mod;
m%=mod;
ans%=mod;
n>>=;
}
return ans;
}
__int64 pow(__int64 a,__int64 n,__int64 mod){
__int64 ans=;
while(n){
if(n&)ans=multi(ans,a,mod);
a=multi(a,a,mod);
ans%=mod;
a%=mod;
n>>=;
}
return ans;
}
int main(){
__int64 f[]={,,,,,,,,,2305843009213693951LL};//存19位最后加LL
__int64 m,a,b,k;
while(scanf("%I64d%I64d%I64d%I64d",&m,&a,&b,&k)!=EOF){
m%=f[k];
printf("%I64d\n",pow(m,a-b,f[k]));
}
return ;
}
上一篇:Python/MySQL(三、pymysql使用)


下一篇:Http的Get和Post--扫盲篇