首页 > ACM题库 > HDU-杭电 > HDU 3930-Broot[解题报告]HOJ
2015
04-14

HDU 3930-Broot[解题报告]HOJ

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);
		}
	}
}