EOJ Mouth 2018.5 D. 无聊的数学题 - 指数循环节

xiaoxiao2021-02-28  3

题解:

当 p 不等于 2 时,我们可以想到的是 

这里给出指数节公式

根据公式

综上

#include<bits/stdc++.h> using namespace std; typedef long long ll; ll n,k,p; ll mut(ll a,ll b,ll mod) { ll ans = 0; while(b) { if(b & 1) ans = (ans + a) % mod; a = (a + a) % mod; b >>= 1; } return ans; } ll power(ll a,ll b,ll mod) { a %= mod; ll ans = 1; while(b) { if(b & 1) ans = mut(ans,a,mod); a = mut(a,a,mod); b >>= 1; } return ans; } ll phi(ll n) { ll ans = n; for(ll i = 2;i*i<=n;i++) { if(n % i == 0) { ans = ans - ans / i; while(n % i == 0) n /= i; } } if(n > 1) ans = ans - ans / n; return ans; } ll inv(ll a,ll mod) { return power(a,mod-2,mod)%mod; } int main() { while(~scanf("%lld%lld%lld",&n,&k,&p)) { ll ans = 0; if(p != 2) { ll phip = phi(p); ll a = power(2,n,phip) + phip; a = power(2,a,p); ll b = power(2,n,p); ans = a * inv(b,p) % p; if(!k) ans--; ans = (ans % p + p) % p; } else { ans = 0; if(!k) ans = 1; } printf("%lld\n",ans); } return 0; }
转载请注明原文地址: https://www.6miu.com/read-2400174.html

最新回复(0)