Submission #50427678

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define op(x) ((x&1)?x+1:x-1)
#define odd(x) (x&1)
#define even(x) (!odd(x))
#define lc(x) (x<<1)
#define rc(x) (lc(x)|1)
#define lowbit(x) (x&-x)
#define mp(x,y) make_pair(x,y)
typedef long long ll;
typedef unsigned long long ull;
typedef double db;
using namespace std;
const ll MAXN = 1e6+10,M = 1e6,INF = 1e18;
ll mypow(ll a,ll n,ll mod){
	ll res = 1,w = a;
	while(n){
		if(n&1)res = res * w%mod;
		w = w*w%mod; n>>=1;
	}
	return res;
}
//
vector<ll>f[MAXN];

ll q,x;

int main(){
	//freopen("in.in","r",stdin);
	//freopen("out.out","w",stdout);

	ios::sync_with_stdio(false); cin.tie(0);

	rep(i,1,2*M){
		if(i%2==0 || i%5==0)continue;
		f[mypow(i,i,M)].push_back(i);
	}

	cin>>q;
	while(q--){
		cin>>x;
		ll mn = INF;

		ll r = x % M;
		for(auto v : f[r]){
			rep(k,0,1000){
				ll val = k*2*M+v;
				if(mypow(val,val,M*1000) == x){
					mn = min(mn,val);
					break;
				}
			}
		}

		if(mn == INF)cout<<"-1\n";
		else cout<<mn<<"\n";
	}

    return 0;
}

Submission Info

Judge Result