幂塔的个位数计算(拓展欧拉定理)

  • 时间:
  • 浏览:
  • 来源:互联网

欧拉定理
若n,a为正整数,且n,a互质,则:
在这里插入图片描述
一个小推论若正整数a与m 互质,则
在这里插入图片描述
拓展欧拉定理
在这里插入图片描述
同时若
在这里插入图片描述
本式子恒成立
在这里插入图片描述
至此,便有了欧拉降幂的模板题

幂塔的个位数计算

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cmath>
#define mode(a,b) a<b?a:a%b+b//欧拉降幂的精髓之处
using namespace std;
typedef long long ll;
ll mp[2102010];
ll ola(ll n){	
	if(mp[n]) return mp[n];
	ll x=n;
	ll s=n;
	for(ll i=2;i<=n/i;i++){
		if(n%i==0){
			s-=s/i;
			while(n%i==0) n/=i;
		}
	}
	if(n>1) s-=s/n;return mp[x]=s;
}//求欧拉函数
ll qmi(ll m, ll k, ll p)
{
    ll res = 1 % p, t = m;
    while (k)
    {
        if (k&1) res = mode(res * t , p);
        t = mode(t * t , p);
        k >>= 1;
    }
    return res;
}
ll solve(ll a,ll b,ll mod){
	if(mod==1||b==1) return mode(a,mod);
	else return qmi(a,solve(a,b-1,ola(mod)),mod);
}
int main(){
	char a[2102020],b[2102002];
	scanf("%s",a);
	scanf("%s",b);
	ll len1=strlen(a);
	ll len2=strlen(b);
	ll aa=a[len1-1]-'0';
	if(len1>1)aa=(a[len1-2]-'0')*10+aa;
    if(len1>2)aa=(a[len1-3]-'0')*100+aa;
	ll bb=b[len2-1]-'0';
	if(len2>1)bb=(b[len2-2]-'0')*10+bb;
    if(len2>2)bb=(b[len2-3]-'0')*100+bb;
    if(aa==0){
        printf("0");
    }else{
		cout<<solve(aa,bb,10)%10;
	}
	return 0;
} 

本文链接http://www.dzjqx.cn/news/show-617342.html