Codeforces Beta Round #17
题目链接：点击我打开题目链接
大概题意：
给你 \(b\)，\(n\)，\(c\).
让你求：\((b)^{n-1}*(b-1)\%c\).
\(2<=b<=10^{10^6},1<=n<=10^{10^6},1<=c<=10^9\)
简明题解：
因为 \(b\) , \(n\)都太大了。关键是求 \((b)^{n-1}\%c\)
所以，我们可以利用欧拉函数 \(phi()\) 的性质。
对于\(a^{b} \% c\) 的形式,我们可以有：
当 \(a\)，\(c\) 互质时有 \(a^{phi(c)} = 1( \mod c)\),
那么经过推导就有（有空写一下 \(Pre-knowledge\)）:
\(a^b\%c=a^{(b\%phi(c))}\). （数论欧拉定理）
但是这个题上并没有说明 \(a\)与 \(c\) 互质。所以不能用这个方法。
所以正解是，我们可以学习一下广义欧拉定理(无互质要求)，用这个来降幂： （广义欧拉定理）：
\(a^b\%c≡a^{(b\%phi(c))\%c}\) \((b<phi(c))\)
\(a^b \%c= a^{(b\%phi(c)+phi(c))\%c}\) （\(b>=phi(c)\)）
然后这题预处理一下 \(phi\)就可以解决了。
复杂度：大概是 \(sqrt(c) * log(c))+log(phi(c))\)
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=1000100;
char b[N],n[N];
int phi(int x)
{
int res=x;
for(int i=2;i*i<=x;i++)if(x%i==0)
{
res=res/i*(i-1);
while(x%i==0)x/=i;
}
if(x>1)res=res/x*(x-1);
return res;
}
int q_pow(int a,int k,int mod)
{
int res=1;
while(k)
{
if(k&1)res=1LL*res*a%mod;
a=1LL*a*a%mod;
k>>=1;
}
return res%mod;
}
int cal(char *str,int mod)
{
int res=0;
for(int i=0;str[i];i++)
{
res=(10LL*res + str[i]-'0') % mod;
}
return res;
}
int main()
{
int c;
scanf("%s%s%d",b,n,&c);
if(c==1)
{
cout<<1<<endl;
exit(0);
}
int B=cal(b,c);
int res=(B + c - 1) % c;
int Phi=phi(c);
int t=0;
for(int i=0;n[i];i++)
{
t = min(1000000000LL,10LL * t + n[i]-'0');
}
if(t - 1 < Phi)
{
res = 1LL * res * q_pow(B,t-1,c)%c;
}
else
{
res = 1LL * res * q_pow(B,cal(n,Phi) + Phi - 1,c)%c;
}
printf("%d\n",(res + c - 1)%c + 1);
return 0;
}
转载于:https://www.cnblogs.com/LzyRapx/p/7738447.html
