扩展欧拉定理
前置芝士
欧拉定理
定义
对于a与m不一定互质的情况，有：
推论
当 (m=1) 时明显成立，接下来讨论 (m ot=1) 的情况。
对于 (gcd(a,m)=1) 的情况，因为 (a^{varphi(m)}equiv 1pmod m) ，所以每 (varphi(m)) 个 (a) 就相当于乘 (1) 。于是只需要算
(cmodvarphi(m)) 次。
对于 (c<varphi(m)) 的情况，直接爆算
下面证明第三种情况。
先证明 (a) 是一个质数的情况：
引理1
(forall p) 为质数，(rin Z^+) ，都有 (varphi(p^r)=(p-1) imes p^{r-1}) 。
证明：
由于p是一个质数，所以 (1sim (p^r-1)) 中有且仅有 (i imes p,iin (0,p^{r-1})) 与 (p^r) 不互质。
于是 (varphi(p^r)=p^r-p^{r-1}=p^{r-1} imes (p-1))
证毕
引理2
(forall~kin Z)，(exists~a,b,x,yin Z^+,x^a imes y^b=k) ，都有 (a,bleqvarphi(k)) 。
证明
先考虑k为一个质数p的r次幂的情况。根据引理1有：
下面说明 ((p-1) imes p^{r-1}geq r) 。
当p=2时：
经验证(~r=1,2,3~)时成立。当(~r>3~)时按照r的大小做数学归纳，可证正确性。
当(~p~>~2~)时，不等号左侧增大，右侧不变，不等式仍然成立。
考虑k是多个质数幂时的情况，按照质数个数做数学归纳，正确性成立。
任意组合质数，引理得证。
证毕
引理三：
(exists~r~leq~c~,a^{varphi(m)+r}~equiv~a^rpmod m。)
证明：
令 (m=t imes a^r) ，其中 (gcd(t,a)=1) ，t的存在性显然
因为 (gcd(t,a)=1) ，且 (varphi) 函数是一个积性函数，所以 (varphi(t)|varphi(m)) 。
根据欧拉定理，(a^{varphi(t)}~equiv~1~pmod t) ，于是：
同余式同乘 (a^r) ，于是：
已经证明可以构造出这样的r。根据引理2，(r~leq~varphi(m))。又 (c~geq~varphi(m))，于是可证构造出的(r~leq~c)。定理得证。
证毕
于是：
对上式做数学归纳，可得(a^c~equiv~a^{c+kvarphi(m)}~,~k~in~Z)，需保证指数为正。
于是最小的合法的指数即为(cmodvarphi(m)~+~varphi(m))。
于是有：
当a是一个质数的幂次时，设 (a=p^k) ，则
当a时多个质数次幂的乘积时，依据唯一分解定理做数学归纳，即证正确性。证毕。
代码
#include <bits/stdc++.h>
#define ll long long
using namespace std;
ll a,m,b;
inline ll read(ll m){
register ll x=0,f=0;char ch=getchar();
while(!isdigit(ch)) ch=getchar();
while(isdigit(ch)){
x=x*10+ch-'0';
if(x>=m) f=1;
x%=m;ch=getchar();
}
return x+(f==1?m:0);
}
ll phi(ll n){
ll ans=n,m=sqrt(n);
for(ll i=2;i<=m;i++){
if(n%i==0){
ans=ans/i*(i-1);
while(n%i==0) n/=i;
}
}
if(n>1) ans=ans/n*(n-1);
return ans;
}
ll fast_pow(ll a,ll b,ll p){
ll ret=1;
for(;b;b>>=1,a=a*a%p)
if(b&1) ret=ret*a%p;
return ret;
}
int main()
{
scanf("%lld%lld",&a,&m);
b=read(phi(m));
printf("%lld
",fast_pow(a,b,m));
return 0;
}
例题
CF17D Notepad
思路
这道题的范围是 (2leq aleq 10^{1000,000}) ，(1leq nleq 10^{1000,000}) ，(1leq pleq 10^9)
一个(a)进制的数字的每一位有(a)种取值，但是题目要求不能有前导0，所以第一位只有(a-1)种取值。
所以满足要求的(a)进制数有 ((a-1)a^{n-1}) 个。
所以题目要求我们求得就是
(但是当 (p|(a-1)a^{n-1}) 时应输出 (p) 。因为此时最后一页有0个字，相当于这一页还没写，也就不是最后一页了)
(a,n) 很大，但是 (pleq 10^9) 。根据扩展欧拉定理，有 (a^{n-1}equiv a^{(n-1)modvarphi(p)+varphi(p)} pmod p) 。所以我们可以边读入边取模。反正 (abmod pequiv(amod p) imes (bmod p)~mod p) 。
#include <cstdio>
#include <cstring>
using namespace std;
typedef long long ll;
const int N=1000010;
char sa[N],sn[N];
ll p,a,n,phi,q,ans;
int len1,len2;
bool flag;
ll power(ll x,ll k)
{
ll ans=1;
for (;k;k>>=1,x=x*x%p)
if (k&1) ans=ans*x%p;
return ans;
}
int main()
{
scanf("%s %s %lld",sa+1,sn+1,&p);
phi=q=p; len1=strlen(sa+1); len2=strlen(sn+1);
for (ll i=2;i*i<=q;i++)
if (!(q%i))
{
phi=phi/i*(i-1);
while (!(q%i)) q/=i;
}
if (q>1) phi=phi/q*(q-1);
for (int i=1;i<=len1;i++)
a=(a*10+sa[i]-48)%p;
for (int i=len2;i>=1;i--) //n-1
if (sn[i]==48) sn[i]='9';
else
{
sn[i]--;
break;
}
for (int i=1;i<=len2;i++)
{
n=n*10+sn[i]-48;
if (n>=phi) flag=1;
n%=phi;
}
if (flag) n+=phi;
ans=((a-1)*power(a,n)%p+p)%p;
if (ans) printf("%lld",ans);
else printf("%lld",p);
return 0;
}