C++(g++ 7.5.0) 解法, 执行用时: 271ms, 内存消耗: 8696K, 提交时间: 2022-10-29 17:03:13

#include<bits/stdc++.h>
#define ll unsigned long long
using namespace std;
ll qm[(1<<20)+50];
int main(){
	ll p, q, k;
	cin >> p >> q >> k;
	while(k--){
		ll a, b, ap, aq;
		scanf("%llu%llu", &a, &b);
		a %= p;
		b %= p;
        ll xa = a;
		memset(qm, -1, sizeof(qm));
        qm[xa%q] = xa;
		for(int i = 0; ; ++i){
            xa = (xa*xa + b) % p;
            if(qm[xa%q] == -1){
                qm[xa%q] = xa;
            }else{
                if(__gcd((xa-qm[xa%q]+p)%p, p) == q) printf("1");
                else printf("0");                
                break; 
            }
		}

	}
	puts("");
}

C++(clang++ 11.0.1) 解法, 执行用时: 265ms, 内存消耗: 8652K, 提交时间: 2022-09-24 22:23:20

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
ll p,q,k;
const int maxn=(1<<20)+5;
ll vis[maxn];
ll gcd(ll a, ll b)
{
	return b?gcd(b,a%b):a;
}
int main()
{
	cin>>p>>q>>k;
	while(k--)
	{
		ull a,b;
		cin>>a>>b;
		a%=p;b%=p;ll x=a;
		memset(vis,-1,sizeof(vis));
		vis[x%q]=x;
		while(true)
		{
			x=(x*x+b)%p;
			if(vis[x%q]!=-1)
			{
				ll delta=(x-vis[x%q]+p)%p;
				if(gcd(delta,p)==q) cout<<"1";else cout<<"0";
				break;
			}
			else vis[x%q]=x;
		}
	}
	return 0;
}