2022杭电多校第二场1009 ShuanQ（数学）

CX is a programmer of a mooc company. A few days ago, he took the blame for leakage of users' data. As a result, he has to develop an encryption algorithm, here is his genius idea.
First, the protocol specifies a prime modulus M, then the server generates a private key P, and sends the client a public key Q. Here Q=P−1,P×Q≡1modM.
Encryption formula: encrypted_data=raw_data×PmodM
Decryption formula: raw_data=encrypted_data×QmodM
It do make sense, however, as a master of number theory, you are going to decrypt it.You have intercepted information about P,Q,encrypted_data, and M keeps unknown. If you can decrypt it, output raw_data, else, say "shuanQ" to CX.

Input

First line has one integer T(T≤20), indicating there are T test cases. In each case:

One line has three integers P,Q,encrypted_data. (1<P,Q,encrypted_data≤2×106)

It's guaranteed that P,Q,encrypted_data<M.

Output

In each case, print an integer raw_data, or a string "shuanQ".

Sample Input

2

5 5 5

6 6 6

Sample Output

shuanQ

1

题目大意：

对于给定的P及其逆元Q以及enc，求由P求Q的mod，并算出P*enc%mod

思路：

对于每对PQ都有唯一的质因数M(M>P&&M>Q)使得P*Q-1==K*M（证伪如下图），这样只需要把P*Q-1的质因数求出来即可

 代码实现：

#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N=100010;
typedef long long LL;
int main(){
	int t;
	cin>>t;
	while(t--){
		LL P,Q,enc,raw=-1;
		cin>>P>>Q>>enc;
		LL KM=P*Q-1,M;
		for(LL i=2;i*i<=KM;i++){
			if(KM%i) continue;
			while(KM%i==0) KM/=i;//保证每次i都是质数 
			M=i;//必定是质数 
		}
		if(KM>1) M=KM;
		if(M>Q&&M>P){
			raw=enc*Q%M;
			cout<<enc*Q%M<<endl;
		}
		else puts("shuanQ");
	}
	return 0;
}