Submission #62137707

---

Source Code Expand

/*
特辣的海藻！！！！！
*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define ull unsigned long long
int MOD;
inline ull qsc(ll a,ll b){
	ll z=(long double)a/MOD*b;
	ll res=(ull)a*b-(ull)z*MOD;
	return (res+MOD)%MOD;
}
inline int qp(int p,int q){
	int ans = 1,pro = p;
	while(q){
		if(q&1)ans = qsc(ans,pro);//(__int128)ans*pro%mod;
		//pro = (__int128)pro*pro%mod;
		pro = qsc(pro,pro);
		q>>=1;
	}
	return ans;
}
vector<int>p;
int n;
int phi;

unordered_map<int,pair<int,int> >mp;
void fenjie(int x,vector<int>& p){
	for(int i = 2;i*i<=x;i++)while(x%i == 0)p.push_back(i),x/=i;
	if(x>1)p.push_back(x);
}
int calc(int x){
	int pro = 1;
	for(int i = 2;i*i<=x;i++){
		if(x%i==0){
			int cc =0 ;
			while(x%i == 0)x/=i,cc++;
			pro = pro*(i-1);fenjie(i-1,p);
			for(int j = 1;j<2*cc;j++)pro = pro*i,fenjie(i,p);
		}
	}
	if(x>1){
		pro = pro*x*(x-1);
		fenjie(x,p),fenjie(x-1,p);
	}
	return pro;
}
int Calc(int X){
	int pro = phi;
	for(auto x:p)if(qp(X,pro/x)==1)pro/=x;
//	assert(qp(X,pro,MOD)==1);
	return pro;
}
void solve(){
	cin >> n;
	if(mp.count(n)){
		auto e = mp[n];
		cout<<e.first<<" "<<e.second <<endl;
		return;
	}
	if(n==1){cout << 1 << " " << 2 << '\n';return;}
	p.clear();
	phi = calc(n);
	int tt = 0,now = 1;
	MOD = n*n;
	while(1){
		++now;
		if(__gcd(now,n)!=1)continue;
		++tt;
		int vv = Calc(now);
		if(vv%n == 0){
			int res = qp(now,vv/n);
			cout << res << " " << MOD << '\n';
			mp[n] = {res,MOD};
			return;
		}
	}
}
signed main(){
	srand(time(0));
	ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
	int t=10000;cin >> t;
	while(t--){
		solve();
	}
}/*

4
3
16
1
55

*/

Submission Info

Judge Result