自动搬运

查看原文

来自洛谷，原作者为

	双管荧光灯 楽園(はめつ)への花道をいざ照らせ

搬运于2025-08-24 22:12:28，当前版本为作者最后更新于2019-10-28 11:44:29，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

神仙题。。。。。。

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

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

令$log_gx=x',log_gy=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");
	}
}