是这样,最近被一道题好好地 # 了一下。
题目:洛谷 AT1357
求n^p%m
其中1<=n、m<=1000000000 1<=p<=100000000000000
该怎办?
不会写快速幂吗
XXXXXXXXXXXXXXXXXXXXX/recordnew/show/6540485
#include<iostream>
using namespace std;
long long qpow(long long a,long long b,long long p)
{
long long ans=1;
while(b>0){
if(b&1)
ans=ans*a%p;
a=a*a%p;
b/=2; }
return ans;}
int main(){
long long b,p,k,ans;
cin>>b>>p>>k;
ans=qpow(b,p,k);
cout<<b<<"^"<<p<<" mod "<<k<<"="<<ans;}<br></p>
我的是这样的
#include<iostream>using namespace std;unsigned long long n,m,p;//n^m%punsigned long long f(unsigned long long x){ if(x==1) return n%p; if(x%2==0) //完全二分 { unsigned long long j=f(x/2); //储存f的值,不用调用2次 return j*j%p; } else { unsigned long long j=f((x-1)/2); return j*j*n%p; }}int main(){ cin>>n>>m>>p; cout<<f(m); return 0;}
时段 | 个数 |
---|---|
{{f.startingTime}}点 - {{f.endTime}}点 | {{f.fileCount}} |
200字以内,仅用于支线交流,主线讨论请采用回复功能。