题解 P5605 【小A与两位神仙】

· · 题解

神仙题。。。。。。

首先指标肯定是求不出来的，BSGS肯定不能想

我们两边分别取以原根为底数的离散对数，方程可化为：

alog_gx \equiv log_gy

令log_gx=x',log_gy=y'

则有方程

ax' \equiv y'(mod\ \phi(m))

可化为：

ax'-b\phi(m) \equiv y'

根据裴蜀定理，则gcd(x',\phi(m))|y'，而这等价于gcd(x',\phi(m))|gcd(y',\phi(m))

所以现在关键就是求gcd(x',\phi(m))

我们找到x的阶a，即最小的a使得x^a \equiv 1 (mod\ m)

令x=g^i（其实这里的i就是x')，则有g^{ia} \equiv 1 (mod\ m)

因为g的阶是\phi(m)，所以phi(m)|ia

设ia=k\phi(m)，由于a是最小的整数使得k也为整数，所以可以得出a=\frac{lcm(i,\phi(m))}{i}，因此a=\phi(m)/gcd(\phi(m),i)

所以gcd(\phi(m),i)=\frac{\phi(m)}{a}

这样就求出gcd(x',\phi(m))了，对y'也同理

所以求出阶就可以快速判断，使用试除法即可在log时间内求出

感谢@rushcheyo神仙的指导QwQ

#include<bits/stdc++.h>
using namespace std;
#define rg register
#define RP(i,a,b) for(register int i=a;i<=b;++i)
#define DRP(i,a,b) for(register int i=a;i>=b;--i)
#define fre(z) freopen(z".in","r",stdin),freopen(z".out","w",stdout)
typedef long long ll;
typedef double db;
#define lll __int128
template<class type_name> inline type_name qr(type_name sample)
{
    type_name ret=0,sgn=1;
    char cur=getchar();
    while(!isdigit(cur))
        sgn=(cur=='-'?-1:1),cur=getchar();
    while(isdigit(cur))
        ret=(ret<<1)+(ret<<3)+cur-'0',cur=getchar();
    return sgn==-1?-ret:ret;
}

ll max_factor;

inline ll gcd(ll a,ll b)
{
    if(b==0)
        return a;
    return gcd(b,a%b);
}

inline ll qp(ll x,ll p,ll mod)
{
    ll ans=1;
    while(p)
    {
        if(p&1)
            ans=(lll)ans*x%mod;
        x=(lll)x*x%mod;
        p>>=1;
    }
    return ans;
}

inline bool mr(ll x,ll b)
{
    ll k=x-1;
    while(k)
    {
        ll cur=qp(b,k,x);
        if(cur!=1 && cur!=x-1)
            return false;
        if((k&1)==1 || cur==x-1)
            return true;
        k>>=1;
    }
    return true;
}

inline bool prime(ll x)
{
    if(x==46856248255981ll || x<2)
        return false;
    if(x==2 || x==3 || x==7 || x==61 || x==24251)
        return true;
    return mr(x,2)&&mr(x,61);
}

inline ll f(ll x,ll c,ll n)
{
    return ((lll)x*x+c)%n;
}

inline ll PR(ll x)
{
    ll s=0,t=0,c=1ll*rand()%(x-1)+1;
    int stp=0,goal=1;
    ll val=1;
    for(goal=1;;goal<<=1,s=t,val=1)
    {
        for(stp=1;stp<=goal;++stp)
        {
            t=f(t,c,x);
            val=(lll)val*abs(t-s)%x;
            if((stp%127)==0)
            {
                ll d=gcd(val,x);
                if(d>1)
                    return d;
            }
        }
        ll d=gcd(val,x);
        if(d>1)
            return d;
    }
}
long long p,o,fa[105],num;
inline void fac(ll x)
{
    if(x<2)
        return;
    if(prime(x))
    {
        fa[++o]=x;
        return;
    }
    ll p=x;
    while(p>=x)
        p=PR(x);
    fac(p),fac(x/p);
}
long long m,tot,x,y,phi,i,j;
int main()
{
    cin>>m>>tot;
    fac(m);
    p=fa[1];
    phi=m/p*(p-1);
    num=o;
    --o;
    fac(p-1);
    sort(fa+1,fa+1+o);
    while(tot--)
    {
        scanf("%lld %lld",&x,&y);
        ll tmp=phi;
        for(i=1;i<=o;)
        {
            for(j=i;j<=o&&fa[i]==fa[j];j++)
            {
                if(qp(x,tmp/fa[i],m)==1)
                    tmp/=fa[i];
                else
                    break;
            }
            for(;j<=o&&fa[i]==fa[j];j++);
            i=j;
        }
        ll t=phi;
        for(i=1;i<=o;)
        {
            for(j=i;j<=o&&fa[i]==fa[j];j++)
            {
                if(qp(y,t/fa[i],m)==1)
                    t/=fa[i];
                else
                    break;
            }
            for(j=i;j<=o&&fa[i]==fa[j];j++);
            i=j;
        }
        tmp=phi/tmp;
        t=phi/t;
        if(t%tmp==0)
            puts("Yes");
        else
            puts("No");
    }
}