UVA 374(Big Mod)大整数 分治
程序员文章站
2022-06-06 20:30:21
...
题意:给出B、P、M,求(B^P)modM。
刚开始想到的是大整数,用Java交了一发,过了……
import java.util.*;
import java.math.*;
public class Main
{
public static void main(String[] args)
{
Scanner input=new Scanner(System.in);
while(input.hasNext())
{
BigInteger B,P,M;
B=input.nextBigInteger();
P=input.nextBigInteger();
M=input.nextBigInteger();
BigInteger ans=B.modPow(P, M);
System.out.println(ans);
}
}
}
由于现在做的是分治专题。所以开始用分治的思路,看了一篇博客,模拟手动运算的代码,照着写了一发,第三个样例运行总是 爆数组,搜了一下其它题解……emmmm……快速幂取模!(卧槽!怎么没想到这个!不过感觉和分治没啥关系)问了一下身边的大佬,好像是有点分治的感觉……
因为这题是对M取模,所以最终结果总是小于M,所以可以用快速幂。记得输入后,B对M取模一下……
#include<bits/stdc++.h>
#define LL long long
using namespace std;
int quickpow(int a,int b,int mod)
{
int ans=1;
while(b)
{
if(b&1)
ans=(ans*a)%mod;
b/=2;
a=(a*a)%mod;
}
return ans;
}
int main()
{
int B,P,M;
while(cin>>B>>P>>M)
{
B%=M;
//P%=M;
cout<<quickpow(B,P,M)<<endl;
}
return 0;
}