本文感谢神仙和神仙的帮助审稿qwq
Definition
\(\forall~a~,~m~\in~Z^+~,~s.t.~\gcd(a,m)=1\)，则一定满足\(~a^{\phi(m)}~\equiv~1~(Mod~m)~\)。该定理被称作欧拉定理。
Demonstration
记\(x_i\)为第\(i\)个与\(m\)互质的数，则共有\(\phi(m)\)个\(x_i\)。
设\(p_i~=~a~\times~x_i\)
引理一：
\(\{p_i\}\)间两两模\(m\)不同余，\(\{x_i\}\)间两两模\(m\)不同余。
证明：
先证\(\{x_i\}\)间两两模\(m\)不同余：
因为\(~\forall~i~\in~[1,\phi(m)]~,~x_i~<~m~\)，故
\[~x_i~Mod~m~\equiv~x_i~\]
又\(~\forall~i,j~\in~[1,\phi(m)],i~\neq~j~\)都有\(~x_i~\neq~x_j~\)。于是
\[~x_i~Mod~m~\neq~x_j~Mod~m~\]
\(\{x_i\}\)间两两模\(m\)不同余
再证\(\{p_i\}\)间两两模\(m\)不同余：
反证法，若存在一对\(~i,j~\in~[1,\phi(m)]~,~i~\neq~j~,~s.t.~p_i~\equiv~p_j~(Mod~m)~\)，则
\[a~\times~x_i~\equiv~a~\times~x_j~(Mod~m)\]
\[\Rightarrow~x_i~\equiv~x_j~(Mod~m)\]。
根据\(\{x_i\}\)间两两模\(m\)不同余，产生矛盾，于是\(\{p_i\}\)间两两模\(m\)不同余
证毕
引理二：
\(\forall~i~\in~[1,\phi(m)]~,~p_i~\)与\(m\)互质。
证明：
写出\(m,a,x_i,p_i\)的唯一分解式：
\[m~=~q_1^{c_1}~q_2^{c_2}~\dots~q_k^{c_k}\]
\[a=q_1^{d_1}~q_2^{d_2}~\dots~q_k^{d_k}\]
\[x_i~=~q_1^{e_1}~q_2^{e_2}~\dots~q_k^{e_k}\]
\[p_i~=~q_1^{e_1+d_1}~q_2^{e_2+d_2}~\dots~q_k^{e_k+d_k}\]
则\(\forall~i~,~s.t.~c_i~\neq~0~\)都有\(d_i~=~e_i~=~0\)，于是\(d_i+e_i~=~0\)。
于是\(\forall~i~\in~[1,\phi(m)]~,~p_i~\)与\(m\)互质。
证毕
根据上述引理，可得所有\(p_i\)的模\(m\)的解的集合与\(\{x_i\}\)相等，于是他们的积模\(m\)的值也相等。
于是有
\[\prod_{i=1}^{\phi(m)}~p_i~\equiv~a^{\phi(m)}~\prod_{i=1}^{\phi(m)}~x_i~\equiv~\prod_{i=1}^{\phi(m)}~x_i~(Mod~m)\]
于是有\(a^{\phi(m)}~\equiv~1~(Mod~m)\)。证毕。
Extension
对于\(a\)与\(m\)不一定互质的情况，有：
\(a^c~\equiv~\begin{cases}a^{c~Mod~\phi(m)} &\gcd(a,m)~=~1 \\a^c &\gcd(a,m)~\neq~1~\land~c~<~\phi(m) \\ a^{c~Mod~\phi(m)~+~\phi(m)} &\gcd(a,m)~\neq~1~\land~c~\geq~\phi(m)\end{cases}\)
Demonstration
当\(m~=~1\)时显然成立，以下讨论\(m~\neq~1\)的情况。
对于\(\gcd(a,m)~=~1~\)的情况，因为\(a^{\phi(m)}~\equiv~1\)，所以每\(\phi(m)\)个\(a\)就相当于乘\(1\)。于是只需要算\(c~Mod~\phi(m)\)次。
对于\(c~<~\phi(m)\)的情况，直接爆算
下面证明第三种情况。
先证明\(a\)是一个质数的情况：
引理1：
\(\forall~p~\)为质数，\(r~\in~Z^+\)，都有\(\phi(p^r)~=~(p-1)~\times~p^{r-1}\)。
证明：
由于\(p\)是一个质数，所以\(~1~\sim~(p^r-1)~\)中有且仅有\(i~\times~p,~i~\in~(0,p^{r-1})~\)与\(p^r\)不互质。
于是\(\phi(p^r)~=~p^r~-~p^{r-1}~=~p^{r-1}~\times~(p~-~1)~\)。
证毕。
引理2：
\(\forall~k~\in~Z\)，\(\exists~a,b,x,y~\in~Z^+~,~s.t.~x^a~\times~y^b~=~k\)，都有\(~a,b~\leq~\phi(k)~\)。
证明：
先考虑\(k\)为一个质数\(p\)的\(r\)次幂的情况。根据引理1有：
\(\phi(k)~=~\phi(p^r)~=~(p-1)~\times~p^{r-1}\)。
下面说明\((p-1)~\times~p^{r-1}~\geq~r\)。
当\(p=2\)时：
经验证\(~r=1,2,3~\)时成立。当\(~r>3~\)时按照\(r\)的大小做数学归纳，可证正确性。
当\(~p~>~2~\)时，不等号左侧增大，右侧不变，不等式仍然成立。
考虑\(k\)是多个质数幂时的情况，按照质数个数做数学归纳，正确性成立。
任意组合质数，引理得证。
证毕
引理3：\(\exists~r~\leq~c~,~s.t.~a^{\phi(m)+r}~\equiv~a^r~(Mod~m)\)。
证明：
令\(m~=~t~\times~a^r\)，其中\(\gcd(t,a)=1\)，\(t\)的存在性显然。
因为\(\gcd(t,a)~=~1\)，且\(\phi\)函数是一个积性函数，所以\(\phi(t)~|~\phi(m)\)。
根据欧拉定理，\(a^{\phi(t)}~\equiv~1~(Mod~t)\)，于是有
\[a^{\phi(m)}~\equiv~1~(Mod~t)\]
同余式同乘\(a^r\)，于是有
\[a^{\phi(m)+r}~\equiv~a^r~(Mod~m)\]
已经证明可以构造出这样的\(r\)。根据引理2，\(r~\leq~\phi(m)\)。又\(c~\geq~\phi(m)\)，于是可证构造出的\(r~\leq~c\)。定理得证。
证毕
于是
\[a^c~\equiv~a^{c-r+r}~\equiv~a^{c-r+\phi(m)+r}~\equiv~a^{c+\phi(m)}~(Mod~m)\]
对上式做数学归纳，可得\(a^c~\equiv~a^{c+k\phi(m)}~,~k~\in~Z\)，需保证指数为正。
于是最小的合法的指数即为\(c~Mod~\phi(m)~+~\phi(m)\)。
于是有\[a^c~\equiv~a^{c~Mod~\phi(m)~+~\phi(m)}\]
当\(a\)是一个质数的幂次时，设\(a=p^k\)，则
\[a^c~\equiv~p^{ck}~\equiv~p^{ck+\phi(m)}~\equiv~p^{ck+k\phi(m)}~\equiv~(p^k)^{c+\phi(m)}~\equiv~(p^k)^{c~Mod~\phi(m)~+~\phi(m)}~~(Mod~m)\]
当\(a\)时多个质数次幂的乘积时，依据唯一分解定理做数学归纳，即证正确性。证毕。
Example
Description
你有一个本子，你要往上面写全部的长度为\(n\)的\(b\)进制数字，每一页可以写\(c\)个。要求所有数字必须严格不含前导\(0\)。求最后一页上有多少个数字
Input
三个数，依次是进制数\(b\),数字长度\(n\)，每一页的个数\(c\)。
Output
一行一个整数代表答案
Hint
\(Forall:\)
\(2~\leq~b~<~10^{10^6}~,~1~\leq~n~<~10^{10^6}~,~1~\leq~c~\leq~10^9\)
Solution
考虑计数原理，第一个位置可以填\(~1~\sim~(b-1)~\)共\(~(b-1)~\)个数字，剩下的位置可以填\(~0~\sim~(~b~-~1~)~\)共\(~b~\)个数字。于是答案即为\(~(b-1)~\times~b^{(n-1)}\)。后面的应用扩展欧拉定理即可解决。
Code
#include#include #define rg register#define ci const int#define cl const long longtypedef long long int ll;template inline void qr(T &x) { rg char ch=getchar(),lst=' '; while((ch > '9') || (ch < '0')) lst=ch,ch=getchar(); while((ch >= '0') && (ch <= '9')) x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); if(lst == '-') x=-x;}namespace IO { char buf[120];}template inline void qw(T x,const char aft,const bool pt) { if(x < 0) {x=-x,putchar('-');} rg int top=0; do {IO::buf[++top]=x%10+'0';} while(x/=10); while(top) putchar(IO::buf[top--]); if(pt) putchar(aft);}const int maxn = 1000010;char B[maxn],N[maxn];ll m,phi,b;int ReadMod(char*,cl&);int GetPhi(ll);void MinuN();int mpow(int,ll);bool judge();int main() { freopen("1.in","r",stdin); scanf("%s %s",B+1,N+1);qr(m); b=ReadMod(B,m); if(judge()) return 0; int k=GetPhi(m); MinuN(); int n=ReadMod(N,k)+k; int ans=1ll*(b-1)*mpow(b,n)%m; ans=(ans+m)%m; qw(ans?ans:m,'\n',true); return 0;}int ReadMod(char *str,cl & p) { int l=strlen(str+1); ll _ret=0; for(rg int i=1;i<=l;++i) _ret=((_ret<<1)+(_ret<<3)+(str[i]^48))%p; return _ret;}int GetPhi(ll x) { ll _ret=x; for(ll i=2;i*i<=x;++i) if(!(x%i)) { _ret=_ret*(i-1)/i; while(!(x%i)) x/=i; } if(x != 1) _ret=_ret*(x-1)/x; return _ret;}void MinuN() { int l=strlen(N+1); --N[l]; for(rg int i=l;i;--i) if(N[i] < '1') { N[i]+=10,--N[i-1]; } else break; if(N[1] == '0'+10) N[1]='0';}int mpow(int x,ll k) { int _ret=1,_temp=x; while(k) { if(k&1) _ret=1ll*_ret*_temp%m; _temp=1ll*_temp*_temp%m; k>>=1; } return _ret%m;}bool judge() { int l=strlen(N+1); if(l >= 17) return false; ll _tp=0; for(rg int i=1;i<=l;++i) _tp=(_tp<<1)+(_tp<<3)+(N[i]^48); int ans=1ll*(b-1)*mpow(b,_tp-1)%m; ans=(ans+m)%m; qw(ans?ans:m,'\n',true); return true;}
Summary
扩展欧拉定理可以用在底数与模数不互质的情况下，将质数将至与模数同阶的大小，从而可以使用快速幂进行运算。
注：本篇内容部分证明参考该，在此表示衷心的感谢。