欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

UVA 374(Big Mod)大整数 分治

程序员文章站 2022-06-06 20:30:21
...

UVA 374(Big Mod)大整数 分治

题意:给出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;
}