#include "math/tetration.hpp"
#pragma once #include<vector> #include<algorithm> #include<cmath> #include"mod_pow.hpp" #include"euler_phi.hpp" /** * @brief テトレーション */ long long tetration(long long a,long long b,long long m){ std::vector<long long> v; long long d=m; while(d!=1){ v.push_back(d); d=euler_phi(d); } v.push_back(1); if(a==0)return (b+1)%2%m; if(m==1)return 0; if(a==1||b==0){ return 1; } if((long long)(v.size())>=b)v.resize(b-1,1); std::reverse(v.begin(),v.end()); long long ans=a; for(auto e:v){ long long ad=(ans<=32&&a<e&&std::pow((double)a,ans)<e?0:e); ans=mod_pow(a%e,ans,e)+ad; } return ans%m; }
#line 2 "math/tetration.hpp" #include<vector> #include<algorithm> #include<cmath> #line 1 "math/mod_pow.hpp" /** * @brief (x^y)%mod */ long long mod_pow(long long x,long long y,long long mod){ long long ret=1; while(y>0) { if(y&1)(ret*=x)%=mod; (x*=x)%=mod; y>>=1; } return ret; } #line 1 "math/euler_phi.hpp" /** * @brief オイラーのファイ関数 */ long long euler_phi(long long n) { long long ret = n; for(long long i=2;i*i<=n;i++) { if(n%i==0) { ret-=ret/i; while(n%i==0)n/=i; } } if(n>1)ret-=ret/n; return ret; } #line 7 "math/tetration.hpp" /** * @brief テトレーション */ long long tetration(long long a,long long b,long long m){ std::vector<long long> v; long long d=m; while(d!=1){ v.push_back(d); d=euler_phi(d); } v.push_back(1); if(a==0)return (b+1)%2%m; if(m==1)return 0; if(a==1||b==0){ return 1; } if((long long)(v.size())>=b)v.resize(b-1,1); std::reverse(v.begin(),v.end()); long long ans=a; for(auto e:v){ long long ad=(ans<=32&&a<e&&std::pow((double)a,ans)<e?0:e); ans=mod_pow(a%e,ans,e)+ad; } return ans%m; }