QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#340521#4395. ShuanQcrsfaa#AC ✓6ms3752kbC++141.0kb2024-02-29 09:39:592024-02-29 09:40:00

Judging History

This is the latest submission verdict.

  • [2024-02-29 09:40:00]
  • Judged
  • Verdict: AC
  • Time: 6ms
  • Memory: 3752kb
  • [2024-02-29 09:39:59]
  • Submitted

answer

#include<bits/stdc++.h>
#define Yukinoshita namespace
#define Yukino std
#define int long long
using Yukinoshita Yukino;
int read()
{
	int s=0,w=1;
	char ch=getchar();
	while(ch<'0'||ch>'9') w=ch=='-'?-1:1,ch=getchar();
	while(ch>='0'&&ch<='9') s=s*10+ch-'0',ch=getchar();
	return s*w;
}
const int mod=998244353;
int qpow(int a,int p)
{
	int mul=1;
	for(;p;p>>=1)
	{
		if(p&1) mul=1ll*mul*a%mod;
		a=1ll*a*a%mod;
	}
	return mul;
}
inline void getmod(int &x)
{
	x-=(x>=mod)*mod;
}
int check(int p,int q,int ed,int mod)
{
	if(p>=mod||q>=mod||ed>=mod) return -1;
	int rd=1ll*ed*q%mod;
	if(1ll*rd*p%mod==ed) return rd;
	return -1;
}
signed main()
{
	int T=read();
	while(T--)
	{
		int p=read(),q=read(),ed=read(),i,v=p*q-1;
		vector<int> res;
		for(i=2;i*i<=v;i++)
			if(v%i==0)
			{
				for(;v%i==0;v/=i);
				int u=check(p,q,ed,i);
				if(~u) res.push_back(u);
			}
		if(v>1)
		{
			int u=check(p,q,ed,v);
			if(~u) res.push_back(u);
		}
		if(res.size()==1) printf("%lld\n",res[0]);
		else puts("shuanQ");
	}
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100
Accepted
time: 6ms
memory: 3752kb

input:

20
5 5 5
6 6 6
882719 680291 233333
989939 479970 53262
938708 679630 425532
984309 264462 254423
669395 343691 43951
574439 394839 546371
599167 899816 782539
756919 648539 507916
925966 1940263 1449550
1733740 811755 1715551
1320129 47186 477900
483330 1684637 108798
1283410 1345854 110616
1817138...

output:

shuanQ
1
38432
698984
592545
974193
758594
258204965
165001059553
shuanQ
57287706
1458297974
shuanQ
5389551
1121735046
1081519
709978395
1606865
14874189
40086026015

result:

ok 20 lines