欧拉降幂 解决极大b的 ab%p
欧拉公式
1∼N中与N互质的数的个数被称为欧拉函数,记为φ(N)。
若在算数基本定理中,N=pa11pa22…pamm,则:
φ(N)=N×p1−1p1×p2−1p2×…×pm−1pm
欧拉定理
(a,n)=1⇒aφ(n)≡1(modn)
费马小定理
p为质数⇒ap−1≡1(modp)
扩展欧拉定理
b<φ(n)时,ab≡ab(modn)
b≥φ(n)时,ab≡abmodφ(n)+φ(n)(modn)
封装函数模板
ll ola_pow(ll a,ll d,ll u,ll p) {
// a^(b)%p b=d^u
// if gcd(a,p)=1 : a^b%p=a^(b%ola(p))%p
// elif b<ola(p) : a^b%p=a^b%p=a^(b%ola(p))%p
// elif b>=ola(p): a^b%p=a^(b%ola(p)+ola(p))%p
ll ola_p=ola(p),ok=0,_=1;
for(ll i=0;i<64&&i<=u;i++) {
if(_>=ola_p) ok=1;
_*=d;
}
return q_pow(a,q_pow(d,u,ola_p)+ok*ola_p,p);
}
欧拉降幂 代码
#define ll long long
ll q_pow(ll n,ll p,ll mod){
ll ans=1;
while(p){
if(p&1) ans=n*ans%mod;
n=n*n%mod;
p>>=1;
}
return ans;
}
ll ola(ll n){ //欧拉函数
ll ans=n;
for(ll i=2;i*i<=n;i++){
if(n%i==0){
ans=ans/i*(i-1);
while(n%i==0) n/=i;
}
}
if(n>1) ans=ans/n*(n-1);
return ans;
}
ll ola_read(ll p){
ll b=0,f=0;
char ch;
while(!isdigit(ch=getchar())) ; //处理缓冲区
while(isdigit(ch)){
b=b*10+ch-'0';
if(b>=p) f=1;
b%=p;
ch=getchar();
}
return b+(f==1)*p;
}
void solve(){ //a^b%p
ll a,p;
cin>>a>>p;
ll b=ola_read(ola(p));
cout<<q_pow(a,b,p);
}
2023河南萌新联赛第(三)场:郑州大学 F
欧拉降幂
首先上面的式子可以分解为:1+x^1+x^2+x^3+x^4+....+x^(2^(n+1)-1)
等比数列求和公式,同时注意公比为1的情况
1.不考虑模数是质数的不简化版本
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll mod=998244353;
ll q_pow(ll a,ll b,ll p=mod){
ll ans=1;
while(b){
if(b&1) ans=(a*ans)%p;
a=(a*a)%p;
b>>=1;
}
return ans;
}
ll ola(ll n){ //欧拉函数
ll res=n;
for(ll i=2;i*i<=n;i++){
if(n%i==0){
res=res/i*(i-1);
while(n%i==0) n/=i;
}
}
if(n>1) res=res/n*(n-1);
return res;
}
ll inv(ll b,ll c=mod){
return q_pow(b,c-2,c);
}
ll ola_pow(ll a,ll d,ll u,ll p) {
// a^(b)%p b=d^u
// if gcd(a,p)=1 : a^b%p=a^(b%ola(p))%p
// elif b<ola(p) : a^b%p=a^b%p=a^(b%ola(p))%p
// elif b>=ola(p): a^b%p=a^(b%ola(p)+ola(p))%p
ll ola_p=ola(p),ok=0,_=1;
for(ll i=0;i<64&&i<=u;i++) {
if(_>=ola_p) ok=1;
_*=d;
}
return q_pow(a,q_pow(d,u,ola_p)+ok*ola_p,p);
}
int main() {
ll n,x;
cin>>n>>x;
x%=mod;
if(x==1) {
cout<<q_pow(2,n+1,mod)<<endl;
}
else {
ll down_q=ola_pow(x,2,n+1,mod);
cout<<((((down_q%mod-1)*inv(x-1))%mod+mod))%mod<<endl;
}
return 0;
}
2.考虑模数为质数的简化版本
#include "bits/stdc++.h"
using namespace std;
using i64 = long long;
constexpr int P = 998244353;
i64 power(i64 a, i64 b, int p = P) {
i64 res = 1;
for (; b; b >>= 1, a = a * a % p) {
if (b & 1) {
res = res * a % p;
}
}
return res;
}
i64 inv(i64 x) {
return power(x, P - 2);
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
i64 n, x;
cin >> n >> x;
x %= P;
if (x == 1) {
cout << power(2, n + 1) << '\n';
} else {
i64 k = power(2, n + 1, P - 1);
cout << (power(x, k) - 1 + P) % P * inv(x - 1) % P << '\n';
}
return 0;
}