P1405题解
Kreado
·
·
题解
题目传送门
刚开始还想暴算，结果炸了……
upd 2024/2/27 修改代码可以通过 hack 数据。
前置知识
思路
给出欧拉定理的结论：
a^{\varphi(m)}\equiv 1 \pmod m ,\gcd(m,a)=1
其中 \varphi(m) 表示小于等于 m 的所有与 m 互质的个数。
给出费马小定理结论：
a^b \equiv a^{b \bmod (p-1)} \pmod p
再给出扩展欧拉定理的结论：
a^{b\bmod \varphi(m)}&,\mathrm{otherwise.}
\end{cases}\pmod m
既然给出结论了，解题就很容易了，直接套用公式。（证明自己网上搜
这里给出如何得到 \varphi(m)：
因为
\varphi(m)=m\prod^n_{i=1}(1-\frac{1}{p_i})
则有以下代码：
```cpp
inline ll Getphi(ll x){
ll res=x;
for(ll i=2;i*i<=x;i++){
if(!(x%i)){
res/=i,res*=(i-1);
while(!(x%i)) x/=i;
}
}
if(x!=1) res/=x,res*=(x-1);
return res;
}
```
因为模数固定，我们可以直接预算出需要用到的欧拉函数。
#### Code
```cpp
#include <bits/stdc++.h>
#define ll long long
using namespace std;
const ll Maxn=1234568;
inline ll ksm(ll a,ll b,ll mod){ll z=1;while(b){if(b&1)z=z*a%mod;a=a*a%mod;b>>=1;}return z;}
ll n,a[Maxn],phi[Maxn];
ll dfs(ll p,ll mod){
if(p==n+1||mod==1) return 1;
ll t=dfs(p+1,phi[mod])+phi[mod];
return ksm(a[p],t,mod);
}
int main(){
scanf("%lld",&n);
phi[10007]=10006;phi[10006]=5002;phi[5002]=2400;phi[2400]=640;phi[640]=256;phi[256]=128;
phi[128]=64;phi[64]=32;phi[32]=16;phi[16]=8;phi[8]=4;phi[4]=2;phi[2]=1;phi[1]=1;
for(ll i=1;i<=n;i++) scanf("%lld",&a[i]);
printf("%lld",dfs(1,10007)%10007);
return 0;
}
```