Luogu

LOJ

分析

因为 $e_1\perp e_2$ ，所以会存在一对数 $s,t$ ，满足 $e_1s+e_2t=1$ 。

我们要求的是 $m\bmod N$ 。我们可以对这个式子做一些变形：
$$
\begin{aligned}
m\bmod N & = m^{e_1s+e_2t}\bmod N \\
& = m^{e_1s}m^{e_2t}\bmod N \\
& = {c_1}^s{c_2}^t\bmod N
\end{aligned}
$$
于是只要求出 $s$ 和 $t$ 即可。因为 $e_1s+e_2t=1$ ，所以可以直接 exgcd 求出 $s$ 和 $t$ 。

然而这里求出的 $s$ 和 $t$ 一正一负，为了方便我们假设 $s$ 是负数。

根据常规方法，有 ${c_1}^{-|s|}\bmod N={c_1}^{\varphi(N)-|s|}\bmod N$ ，然而求 $\varphi(N)$ 的复杂度过大，所以这样是不行的。

根据小学奥数可以得到 ${c_1}^{-|s|}\bmod N=\left(c_1^{-1}\right)^{|s|}\bmod N$ ，于是我们只要求出 $c_1^{-1}$ 即可。

设 $d=c_1^{-1}\bmod N$ ，可以得到 $c_1d+kN=1$ 。那么直接 exgcd 求出 $d$ 即可。

代码

// ===================================
//   author: M_sea
//   website: http://m-sea-blog.com/
// ===================================
#include <algorithm>
#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>
#include <cmath>
#define re register
#define int long long
using namespace std;

inline int read() {
    int X=0,w=1; char c=getchar();
    while (c<'0'||c>'9') { if (c=='-') w=-1; c=getchar(); }
    while (c>='0'&&c<='9') X=X*10+c-'0',c=getchar();
    return X*w;
}

int c1,c2,e1,e2,mod;

inline int exgcd(int a,int b,int& x,int& y) {
    if (!b) { x=1,y=0; return a; }
    int d=exgcd(b,a%b,x,y);
    int z=x; x=y,y=z-y*(a/b);
    return d;
}

inline int mul(int a,int b) {
    int d=(int)((long double)a/mod*b+0.5);
    return (a*b-d*mod+mod)%mod;
}

inline int qpow(int a,int b) {
    int c=1;
    for (;b;b>>=1,a=mul(a,a)) if (b&1) c=mul(a,c);
    return c;
}

signed main() {
    int T=read();
    while (T--) {
        c1=read(),c2=read(),e1=read(),e2=read(),mod=read();
        int s,t; exgcd(e1,e2,s,t);
        while (t<0) t+=e1,s-=e2;
        int d,tmp; exgcd(c1,mod,d,tmp);
        printf("%lld\n",mul(qpow(d,-s),qpow(c2,t)));
    }
    return 0;
}