2015
04-14

# Broot

There is a way of encryption in the Digital planet. If the number x, who lives in M area, K layer, then it will change its name to x ^ K mod M, that is newx = x ^ k mod m. Now the Digital Kingdom wants to make a program, which can find all the original number of a name living in some area, some layer. If there is no solution, output -1.

There are multiply test cases. Each test case contains there integers k, m , newx ,(0 <= newx , m ,k <= 1.5*10^15) , m is a prime number.

There are multiply test cases. Each test case contains there integers k, m , newx ,(0 <= newx , m ,k <= 1.5*10^15) , m is a prime number.

1 5 4
2 13 8
3 13 8

case1:
4
case2:
-1
case3:
2
5
6

/*===========================================
|	hdu3323幂次方程:
|		x^q = a (%p) 已知q,a,p,求x. p为素数
| 方法：先找到p的原跟g（暴力枚举然后验证）。
|		 用baby_step求解 g^T = a(%p) 的解T。
| 然后由于q*k % Eular(p) = T 可由欧拉公式g^Eular(p)=1推得.
| (Eular(p)为原跟g的幂的周期)
| 于是解出(T,Eular(p))个解k，然后答案就是g^k
============================================*/
#include<stdio.h>
#include<vector>
#include<math.h>
#include<string.h>
#include<algorithm>
#include<iostream>
#include<cassert>

#define PB push_back
#define MP make_pair
using namespace std;
typedef long long ll;

const ll hsz = 1999997;
vector< pair<ll,int> > has[hsz];

vector<ll> fac;
ll tot;

ll mul(ll a,ll x,ll mod)
{
ll rec = 0;
while (x){
if (x&1) rec = (rec + a) % mod;
a = (a + a) % mod;
x >>= 1;
}
return rec;
}
ll quick_pow(ll a,ll x,ll mod)
{
ll rec = 1;
while (x)
{
if (x&1) rec = mul(rec, a, mod);
a = mul(a, a, mod);
assert(a >= 0);
assert(rec >= 0);
x >>= 1;
}
return rec;
}
bool check(ll x,ll y,ll mod)
{
//cout << "check " << x << " " << y << " " << mod << endl;
for (int i=0;i<fac.size();i++)
{
if (quick_pow(x, y/fac[i], mod) == 1)
return false;
}
return true;
}
ll findori(ll p)
{
ll x = p - 1;
fac.clear();
for (int i=2;(ll)i*i<=x;i++)
if (x % i == 0)
{
fac.push_back(i);
while (x % i == 0) x /= i;
}

if (x > 1) fac.push_back(x);

//for (int i=0;i<fac.size();i++) printf("%d ",fac[i]); printf("\n");

for (int i=2;i<p;i++)
if (check(i, p-1, p))
return i;

return -1;
}
ll ex_gcd(ll a,ll b,long long &x,long long &y)
{
ll t,rec;
if (b == 0)
{
x = 1;
y = 0;
return a;
}
rec = ex_gcd(b,a%b,x,y);
t = x;
x = y;
y = t- a/b*y;
return rec;
}
ll hash(ll x,int id)
{
int v = x % hsz;
for (int i=0;i<has[v].size();i++)
if (has[v][i].first == x)
return has[v][i].second;

if (id > -1)
{
has[v].PB(MP(x, id));
//cout << "insert is " << x << " " << id << endl;
}
return -1;
}
ll ni(ll a,ll p)
{
long long x,y;
ex_gcd(a,p,x,y);
return (x % p + p) % p;
}
vector<ll> ret;
vector<ll> mod_equ(ll a,ll b,ll n)
{
ret.clear();
long long x,y;
ll d = ex_gcd(a,n,x,y);
if (b % d == 0)
{
x = x * (b/d) % n;
if ( x<0 ) x += n;
for (ll i=0;i<d;i++)
ret.push_back(x + i*(n/d));
}
return ret;
}
vector<ll> ans,tmp;
ll solve(ll g,ll q,ll p,ll a)
{
ll m = (long long)ceil(sqrt(p*1.0));

//for (int i=0;i<hsz;i++) has[i].clear();
//cout << "m is " << m << endl;

ll ret = 1;
for (int i=0;i<m;i++)
{
hash(ret, i);
ret = mul(ret, g, p);
}

//cout << "out!!!!!!!!!!!!!\n";

ll pro = 1;
ll step = ret;
ans.clear();
for (int i = 0;i < m;i++, pro = pro * step % p)
{
ll num = a * ni(pro,p) % p;
ll j = hash(num, -1);
if (j != -1)
{
ll k = i * m + j;
tmp = mod_equ(q, k, p-1);
for (int e=0;e<tmp.size();e++)
ans.push_back( quick_pow(g, tmp[e], p) );
break;
}
}
if (ans.size() == 0)
printf("-1\n");
else
{
sort(ans.begin(),ans.end());
for (int i=0;i<ans.size();i++)
cout << ans[i] << endl;
}

ret = 1;
for (int i=0;i<m;i++)
{
has[(int)(ret%hsz)].clear();
ret = mul(ret, g, p);
}
}
int main()
{
long long p, q, a;
int cas = 0;
while (cin >> q >> p >> a)
{
printf("case%d:\n",++cas);
if (a == 0)
printf("0\n");
else
{
ll g = findori(p);
//cout << "g is " << g << endl;
solve(g, q, p, a);
}
}
}