欧拉降幂公式 -一个渣渣

欧拉定理

如果正整数a , n 互质 gcd(a,n) = 1 , 则 $a^{\phi (n)}\equiv 1 (mod n)$ , 其中 $\phi$ 是欧拉函数。

推论 :

如果正整数 a, n 互质 ,则对于任意正整数 b , 有 $a^{b} \equiv a^{b (mod) \phi(n) } (mod ) n$ .

降幂公式

模板题 : 点击

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std ;
typedef long long LL;
char b[1000006] ;
LL a ,c ;
LL qpower(LL a ,LL b ,LL mod ) {
    LL ans = 1 ;
    while(b){
        if(b&1) {
            ans = ans* a%mod ;
        }
        a = a*a %mod ;
        b>>=1 ;
    }
    return ans %mod;
}
LL phi(LL n) { // 求单个值的欧拉函数
	LL ans = n ;
	for(int i = 2 ; i*i<=n ; i++ ) {
		if(!(n%i)){
			ans = ans/i*(i-1) ;
			while(n%i == 0 ){
				n/=i ;
			}
		}
	}
	if(n>1) ans = ans/n*(n-1) ;
	return ans ;
}

int main(){

	while(~scanf("%lld %s %lld",&a,b,&c)){
		LL len = strlen(b) ;
		LL p = phi(c) ;
		LL ans = 0 ;
		for(LL i = 0 ; i<len ; i++){
			ans = (ans*10 +b[i] -'0')%p ;
		}
		ans +=p ;
		printf("%lld\n",qpower(a,ans,c));
		
	}




    return 0 ;
}

参考 : https://blog.csdn.net/qq_37632935/article/details/81264965

转载自原文链接, 如需删除请联系管理员。

原文链接：欧拉降幂公式，转载请注明来源！