网站平台建设的重要性,响应式网站切图,小企业怎么做网站,网站添加设置着陆页2023牛客暑期多校训练营9-B Semi-Puzzle: Brain Storm
https://ac.nowcoder.com/acm/contest/57363/B 文章目录 2023牛客暑期多校训练营9-B Semi-Puzzle: Brain Storm题意解题思路代码 题意 解题思路
欧拉定理 a b ≡ { a b % φ ( p ) g c d ( a , p ) 1 a b g c d ( a ,…2023牛客暑期多校训练营9-B Semi-Puzzle: Brain Storm
https://ac.nowcoder.com/acm/contest/57363/B 文章目录 2023牛客暑期多校训练营9-B Semi-Puzzle: Brain Storm题意解题思路代码 题意 解题思路
欧拉定理 a b ≡ { a b % φ ( p ) g c d ( a , p ) 1 a b g c d ( a , p ) ≠ 1 , b φ ( p ) a b % φ ( p ) φ ( p ) g c d ( a , p ) ≠ 1 , b ≥ φ ( p ) a^b\equiv \begin{cases} a^{b\%\varphi(p)}~~gcd(a,p)1\\ a^b~~gcd(a,p)\neq 1,b\varphi(p)\\ a^{b\%\varphi(p)\varphi(p)}~~gcd(a,p)\neq 1,b\ge\varphi(p) \end{cases} ab≡⎩ ⎨ ⎧ab%φ(p) ab ab%φ(p)φ(p) gcd(a,p)1gcd(a,p)1,bφ(p)gcd(a,p)1,b≥φ(p) a u ≡ u ( m o d p ) 设 d u % φ ( p ) φ ( p ) u d k φ ( p ) a d k φ ( p ) ≡ d k φ ( p ) ( m o d p ) a d − d ≡ k φ ( p ) ( m o d p ) \begin{matrix} a^u\equiv u\pmod p\\ 设du\%\varphi(p)\varphi(p)\\ udk\varphi(p)\\ a^{dk\varphi(p)}\equiv dk\varphi(p)\pmod p\\ a^d-d\equiv k\varphi(p)\pmod p \end{matrix} au≡u(modp)设du%φ(p)φ(p)udkφ(p)adkφ(p)≡dkφ(p)(modp)ad−d≡kφ(p)(modp) 将取余打开可得 φ ( p ) x p y a d − d \begin{matrix} \varphi(p)xpya^d-d \end{matrix} φ(p)xpyad−d 显然可以用扩展欧几里得求解当 φ ( p ) x p y gcd ( p , ϕ ( p ) ) \varphi(p)xpy\gcd(p,\phi(p)) φ(p)xpygcd(p,ϕ(p))的解为保证 d d d有解故 gcd ( p , φ ( p ) ) ∣ a d − d \gcd(p,\varphi(p))\mid a^d-d gcd(p,φ(p))∣ad−d设 a d − d h gcd ( φ ( p ) , p ) a^d-dh\gcd(\varphi(p),p) ad−dhgcd(φ(p),p)故 a d h gcd ( φ ( p ) , p ) d a^dh\gcd(\varphi(p),p)d adhgcd(φ(p),p)d可以发现 a d ≡ d ( m o d gcd ( φ ( p ) , p ) ) a^d\equiv d\pmod{\gcd(\varphi(p),p)} ad≡d(modgcd(φ(p),p))可以发现形式上与 a u ≡ u ( m o d p ) a^u\equiv u\pmod p au≡u(modp)显然当 p 1 p1 p1时 u 0 u0 u0有了边界条件可以递归求出 u u u。 u d k φ ( p ) udk\varphi(p) udkφ(p) k k k即为 φ ( p ) x p y a d − d \varphi(p)xpya^d-d φ(p)xpyad−d中 x x x的解当求出 φ ( p ) x 0 p y 0 gcd ( p , ϕ ( p ) ) \varphi(p)x_0py_0\gcd(p,\phi(p)) φ(p)x0py0gcd(p,ϕ(p)): x x 0 × ( a d − d gcd ( φ ( p ) , p ) % p ) x 0 × ( ( a d − d ) % p gcd ( φ ( p ) , p ) ) \begin{matrix} xx_0\times(\dfrac{a^d-d}{\gcd(\varphi(p),p)}\% p)\\ x_0\times(\dfrac{(a^d-d)\% p}{\gcd(\varphi(p),p)}) \end{matrix} xx0×(gcd(φ(p),p)ad−d%p)x0×(gcd(φ(p),p)(ad−d)%p)
代码
#includebits/stdc.h
#define ll long long
#define pii pairint,int
using namespace std;
ll T,a,m;
ll phi(ll n){ll sumn;for(ll i2;i*in;i){if(n%i0){while(n%i0)n/i;sum/i,sum*i-1;}}if(n1)return sum/n*(n-1);return sum;
}
ll exgcd(ll a,ll b,ll x,ll y){if(!b){x1,y0;return a;}ll vexgcd(b,a%b,y,x);y-a/b*x;return v;
}
ll power(ll x,ll p,ll mod){ll res1;while(p){if(p1)res*x,res%mod;x*x,x%mod;p1;}return res;
}
ll dfs(ll a,ll p){if(p1)return 0;ll phphi(p);ll x,y;ll vexgcd(ph,p,x,y);x(x%pp)%p;ll ddfs(a,v)ph;return d(x*((power(a%p,d,p)-d%pp)%p/v)%p)*ph;
}
void solve(){cinam;ll xdfs(a,m);coutx\n;
}
int main(){cinT;while(T--)solve();
}
