这是一道数论题数论题数论题(重要的事情说3遍QAQ)
因为这道题的数据过为奇葩巨大,因此不能
int a,b,p,ans=1;
cin>>a>>b>>p;
for(int i=0;i<b;i++)ans=ans*a%p;
cout<<ans<<endl;
然后就 Time Limit Enough Exceed 了
那 what should us do 呢?
我们需要一个快速幂
快速幂又是什么Na?
众所周知,一个十进制数可以由二进制数 2^0 , 2^1……等表示出来
因此,a^n中的n用二进制数biu示出来后(方法如下)
f[c]=1;c++;f[c]=a%p;c++;
for(long long q=2;q<=b;q*=2)
{
f[c]=(f[c-1]*f[c-1])%p;
c++;
}
a的n次方也可以算la!
CODE
#include<iostream>
using namespace std;
long long a,b,p,f[102],c,ans=1;
int main()
{
cin>>a>>b>>p;
f[c]=1;c++;f[c]=a%p;c++;
for(long long q=2;q<=b;q*=2)
{
f[c]=(f[c-1]*f[c-1])%p;
c++;
}
while(b)
{
int k=b&(-b);int wz=0;
b-=k;
while(k)
{
k=k>>1;
wz++;
}
ans=(ans*f[wz])%p;
}
cout<<ans%p<<endl;
return 0;
}
$\frac{30}{\sqrt{50}}$
$log 2 n$
$log(2,n)$
$log(2,n)
???