https://ac.nowcoder.com/acm/contest/9981/H
思路:歐拉降冪，
由于沒怎么接觸，補一下這塊知識，
由于我們取個位數，所以對于本題目來說是mod10(p=10)
至于歐拉降冪的遞回形式，就是如下面兩個圖所示.
舉個小例子模擬一下:
還有一個問題，我們都是整數，這個題這么大，怎么看取多少位呢，
mod10遞回幾次就結束了，我們打不了取100層，
對于這個底數a，我們要觀察，對于其%2這一層，相當于判奇偶，只要知道個位，
對于%4，則要個位和十位，解釋:比如一個三位數x,那么其可以拆分成(k*100+num)%4=k*100%4+num%4；前者的mod為0；所以只考慮后者的num,也就是十位和百位，
我們對底數a取兩位就好，
剩下來就是部分板子，
#include<iostream>
#include<vector>
#include<queue>
#include<cstring>
#include<cmath>
#include<map>
#include<set>
#include<cstdio>
#include<algorithm>
#define debug(a) cout<<#a<<"="<<a<<endl;
using namespace std;
const int maxn=1e5+1000;
typedef long long LL;
inline LL read(){LL x=0,f=1;char ch=getchar(); while (!isdigit(ch)){if (ch=='-') f=-1;ch=getchar();}while (isdigit(ch)){x=x*10+ch-48;ch=getchar();}
return x*f;}
LL phi[maxn],primes[maxn],cnt;
bool v[maxn];
void Euler(LL num){
for(LL i=2;i<num;i++){
if(!v[i]){
primes[++cnt]=i;
phi[i]=i-1;
}
for(LL j=1;j<=cnt;j++){
if(primes[j]*i>num) break;
v[primes[j]*i]=1;
if(i%primes[j]==0) {
phi[i*primes[j]]=phi[i]*primes[j];
break;
}
phi[i*primes[j]]=phi[i]*(primes[j]-1);
}
}
phi[1]=1;
}
LL q_pow(LL a,LL b,LL p){
LL res=1;
while(b){
if(b&1) res=res*a>p?res*a%p+p:res*a;
b>>=1;
a=a*a>p?a*a%p+p:a*a;
}
return res;
}
LL solve(LL a,LL b,LL m){
if(m==1||b==0) return 1;///phi(m)<m,所以m最后為1
return q_pow(a,solve(a,b-1,phi[m]),m);
}
int main(void)
{
Euler(100000);
LL mod=10;
string s1,s2;cin>>s1>>s2;
LL len1=s1.size();LL len2=s2.size();
LL a=0;
for(LL i=max((LL)0,len1-3+1);i<len1;i++){
a=a*10+(s1[i]-'0');
}
LL b=0;
if(len2>=3) b=100;
else{
for(LL i=0;i<len2;i++){
b=b*10+(s2[i]-'0');
}
}
/// debug(a);debug(b);debug(mod);
cout<<solve(a,b,mod)%mod<<"\n";
return 0;
}
轉載請註明出處，本文鏈接：https://www.uj5u.com/qita/256690.html
標籤：其他
上一篇：nginx筆記(更新中)
下一篇：JavaScript_數字時鐘