三亚旅游网站建设,北京网站建设,外贸营销推广公司,手机购物网站设计文章目录 题目大意题解求解回溯 参考代码 题目大意
给定两个数 a , m a,m a,m #xff0c;求满足 a u ≡ u ( m o d m ) a^u \equiv u (mod\ \ m) au≡u(mod m) 的一个解。 ( 1 ≤ a , m ≤ 1 0 9 , 0 ≤ u ≤ 1 0 18 ) (1\leq a,m \leq10^9 ,0\leq u\leq 10^{18}) (1≤a… 文章目录 题目大意题解求解回溯 参考代码 题目大意
给定两个数 a , m a,m a,m 求满足 a u ≡ u ( m o d m ) a^u \equiv u (mod\ \ m) au≡u(mod m) 的一个解。 ( 1 ≤ a , m ≤ 1 0 9 , 0 ≤ u ≤ 1 0 18 ) (1\leq a,m \leq10^9 ,0\leq u\leq 10^{18}) (1≤a,m≤109,0≤u≤1018)
题解
参考了讨论区 https://blog.nowcoder.net/n/576f9463036346f0a0fb04fee50fac75 的方法
求解
考虑使用欧拉定理考虑 b ϕ p b\phi_p bϕp的情况。 a u ≡ { a u % ϕ m g c d ( a , u ) 1 a u % ϕ i ϕ m g c d ( a , u ) ! 1 ( m o d m ) a^u\equiv\begin{cases}a^{u\% \phi_m }gcd(a,u)1\\a^{u\% \phi_i\phi_m} gcd(a,u)!1\end{cases}(mod \ m) au≡{au%ϕmau%ϕiϕmgcd(a,u)1gcd(a,u)!1(mod m) 定义 d u % ϕ m du\%\phi_m du%ϕm 或 u % ϕ m ϕ m u\%\phi_m\phi_m u%ϕmϕm 和 k ∗ ϕ p d u ( k 0 ) k*\phi_pdu(k0) k∗ϕpdu(k0) 则原式可以转化为 a d ≡ d k ∗ ϕ m ( m o d m ) a^d \equiv dk*\phi_m (mod\ m) ad≡dk∗ϕm(mod m) 移项可以得到 a d − d ≡ k ∗ ϕ m ( m o d m ) a^d-d\equiv k*\phi_m(mod\ m) ad−d≡k∗ϕm(mod m) ϕ m ∗ x 1 m ∗ y 1 ≡ g c d ( ϕ m , m ) ( m o d m ) \phi_m*x1m*y1\equiv gcd(\phi_m,m) (mod \ m) ϕm∗x1m∗y1≡gcd(ϕm,m)(mod m) 是一个已知有解的同余方程 回到上一个方程想要得到解 k k k 显然要满足 a d − d x ∗ g c d ( m , ϕ m ) , ( x 0 ) a^d-dx *gcd(m,\phi_m),(x0) ad−dx∗gcd(m,ϕm),(x0) 也就是 a d ≡ d ( m o d g c d ( m , ϕ m ) ) a^d \equiv d (mod \ gcd(m,\phi_m)) ad≡d(mod gcd(m,ϕm))。 重新得到了题目但是模数缩小了因此我们想到了递归直到模数为 1 1 1 时直接推出答案。
回溯
假设我们已经得到了最后一组解 d 0 d0 d0 求解同余方程 a d − d ≡ k ∗ ϕ m ( m o d m ) a^d-d\equiv k*\phi_m(mod\ m) ad−d≡k∗ϕm(mod m)使用扩展欧几里得定理推出 x 1 x1 x1 的值 k x 1 ∗ a d − d g c d ( m , ϕ m ) % m o d kx1*\frac{a^d-d}{gcd(m,\phi_m)}\%mod kx1∗gcd(m,ϕm)ad−d%mod 由于 a d a^d ad 超出范围根据 a b % ( b ∗ c ) a % ( b ∗ c ) b \frac{a}{b}\%(b*c)\frac{a\%(b*c)}{b} ba%(b∗c)ba%(b∗c)得出 k x 1 ∗ ( a d − d ) % m / ϕ m kx1*(a^d-d)\%m/\phi_m kx1∗(ad−d)%m/ϕm 。 再利用 k ∗ ϕ p d u k*\phi_pdu k∗ϕpdu得出结果即可。
参考代码
#includebits/stdc.h
#define ll long long
using namespace std;
ll phi(ll x)
{ll ansx;for(int i2;i*ix;i){if(x%i0)ansans/i*(i-1);while(x%i0)x/i;}if(x!1)ansans/x*(x-1);return ans;
}
ll ksm(ll a,ll b,ll p)
{ll res1;while(b){if(b1)resres*a%p;aa*a%p;b1;}return res;
}
ll exgcd(ll a,ll b,ll x,ll y)
{if(!b){x1,y0;return a;}ll kexgcd(b,a%b,y,x);y-a/b*x;return k;
}
int n,T;
ll a,m;
ll work(ll a,ll p) //递归求解
{if(p1)return 0;ll mphi(p);ll bwork(a,__gcd(m,p))m;ll x,y;ll dexgcd(m,p,x,y);ll k(((x*(ksm(a,b,p)-bp))%pp)%p/d); //回溯求值return k*mb;
}
int main()
{cinT;while(T--){scanf(%lld%lld,a,m);printf(%lld\n,work(a,m));}
}
