P5091 【模板】扩展欧拉定理 题解

博客园同步

原题链接

前置知识：

欧拉筛，一些基本数论知识。

简要题意：

求 $a^b\%m$.

$1\le a\le 10^9,1\le b\le 10^{2\times 10^7},1\le m\le 10^8$.

首先，看到这个数据范围你就发现你凉凉了。

算法一

一个简单的弱化：

$a,b,m\le 10^7$.

显然你 $\mathcal{O}(b)$ 过了。

算法二

一个再简单点的强化呢：

. $a,b,m\le 10^{18}$.

你用 $\mathcal{O}(\log b)$ 可以飞快过了 。

算法三

那么考虑这道题目呢？不行了吧？

可能，$\mathcal{O}(\log b)$ 的朴素快速幂 $+$ 每次 $b$ 的高精度除法 $÷2$ $+$ 一定卡常是可以通过的。

但是我们不要，我们只需要用一个简单的定理：

$$a^b\equiv \{\begin{array}{l}{a}^b,b<\varphi (m)\\ a^{b\text{mod}\varphi (m)+\varphi (m)},b\ge \varphi (m)\end{array}$$

先不管如何证明，考虑用这个玩意儿怎么做。

用 $\mathcal{O}(\sqrt{m})$ 的时间可以算出 $\varphi (m)$，然后快读 $b$，$b\le \varphi (m)$ 则套公式快速幂，如果 $b<\varphi (m)$ 只能说明 $b$ 也很小，再跑一个 $\log$ 也没啥问题了。

具体证明大家可以去看一下 $\text{ouuan}$ 的博客

#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; #define int long long inline int read(){char ch=getchar(); int f=1; while(ch<'0' || ch>'9') {if(ch=='-') f=-f; ch=getchar();} int x=0; while(ch>='0' && ch<='9') x=(x<<3)+(x<<1)+ch-'0',ch=getchar(); return x*f;} inline int remo(int m) { char c; while(!isdigit(c=getchar())); int x=0; bool f=0; for(;isdigit(c);c=getchar()) { x=x*10+c-'0'; if(x>=m) f=1,x%=m; } return f?(x+m):x; } inline void write(int x) { if(x<0) {putchar('-');write(-x);return;} if(x<10) {putchar(char(x%10+'0'));return;} write(x/10);putchar(char(x%10+'0')); } inline int pw(int a,int b,int m) { int ans=1; while(b) { if(b&1) ans=ans*a%m; a=a*a%m; b>>=1; } return ans; } signed main() { int a=read(),m=read(); a%=m; int phi=1,t=m,ans=1; for(int i=2;i*i<=t;i++) { if(t%i) continue; phi*=i-1; t/=i; while(t%i==0) phi*=i,t/=i; } if(t>1) phi*=t-1; //printf("%d\n",remo(phi)); printf("%d\n",pw(a,remo(phi),m)); return 0; }