描述
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 ;
}