华华教月月做数学(快速幂+快速乘）

题目描述

找到了心仪的小姐姐月月后，华华很高兴的和她聊着天。然而月月的作业很多，不能继续陪华华聊天了。华华为了尽快和月月继续聊天，就提出帮她做一部分作业。
月月的其中一项作业是：给定正整数A、B、P，求ABmodPABmodP的值。华华觉得这实在是毫无意义，所以决定写一个程序来做。但是华华并不会写程序，所以这个任务就交给你了。
因为月月的作业很多，所以有T组询问。

输入描述:

第一行一个正整数T表示测试数据组数。
接下来T行，每行三个正整数A、B、P，含义如上文。

输出描述:

输出T行，每行一个非负整数表示答案。

示例1

输入

复制

2
2 5 10
57284938291657 827493857294857 384729583748273

输出

复制

2
18924650048745

备注:

1≤T≤1031≤T≤103，1≤A,B,P≤10181≤A,B,P≤1018
   快速幂加快速乘模板题。

 1 #include<iostream>
 2 #include<vector>
 3 #include<string>
 4 #include<cstring>
 5 #include<cmath>
 6 #include <algorithm>
 7 #include <stdlib.h>
 8 #include <cstdio>
 9 #include<sstream>
10 #include<cctype>
11 #include <set>
12 #include <map>
13 #define ll long long
14 using namespace std;
15 ll fastc(ll a,ll b,ll c)
16 {
17     ll ans=0;
18     a%=c;
19     while(b)
20     {
21         if(b&1) ans=(a+ans)%c;
22         a=(a+a)%c;
23         b>>=1;
24     }
25     return ans%c;
26 }
27 ll fastpower(ll base,ll power,ll p)
28 {
29     ll res=1;
30     while(power>0)
31     {
32         if(power&1) res=fastc(res,base,p);
33         power>>=1;
34         base=fastc(base,base,p);
35     }
36     return res;
37 };
38 int main()
39 {
40     ll t,n,m,p;
41     cin>>t;
42     while(t--)
43     {
44         cin>>n>>m>>p;
45         cout<<fastpower(n,m,p)<<endl;
46     }
47 }

View Code

下面是（01）快速乘

 1 #include<iostream>
 2 #include<vector>
 3 #include<string>
 4 #include<cstring>
 5 #include<cmath>
 6 #include <algorithm>
 7 #include <stdlib.h>
 8 #include <cstdio>
 9 #include<sstream>
10 #include<cctype>
11 #include <set>
12 #include <map>
13 #define ll long long
14 using namespace std;
15 inline ll fastc(ll a,ll b,ll c)
16 {
17     return (a*b-(ll)((long double)a/c*b)*c+c)%c;
18 }
19 ll fastpower(ll base,ll power,ll p)
20 {
21     ll res=1;
22      base%=p;//特别注意，不加这句错
23     while(power>0)
24     {
25         if(power&1) res=fastc(res,base,p);
26         power>>=1;
27         base=fastc(base,base,p);
28     }
29     return res;
30 };
31 int main()
32 {
33     ll t,n,m,p;
34     cin>>t;
35     while(t--)
36     {
37         cin>>n>>m>>p;
38         cout<<fastpower(n,m,p)<<endl;
39     }
40 }

View Code

 1 #include<iostream>
 2 #include<vector>
 3 #include<string>
 4 #include<cstring>
 5 #include<cmath>
 6 #include <algorithm>
 7 #include <stdlib.h>
 8 #include <cstdio>
 9 #include<sstream>
10 #include<cctype>
11 #include <queue>
12 #include <map>
13 #define ll long long
14 using namespace std;
15  ll fastc(ll a, ll b, ll Mod)
16 {
17     ll c =( a*b)-(ll)((long double)a*b/Mod+0.5)*Mod;
18     return c<0 ? c+Mod : c; 
19 }
20 ll fastpower(ll base,ll power,ll p)
21 {
22     ll ans=1;
23     base%=p;//不加通不过
24     while(power)
25     {
26         if(power&1) ans=fastc(ans,base,p);
27         power>>=1;
28         base=fastc(base,base,p);
29     }
30     return ans%p;
31 }
32 int main()
33 {
34     ll n,m,t,p;
35     cin>>t;
36     while(t--)
37     {
38         cin>>n>>m>>p;
39         cout<<fastpower(n,m,p)<<endl;
40     }
41 }

View Code