某岛

… : "…アッカリ~ン . .. . " .. .
March 30, 2011

SPOJ 3105. Power Modulo Inverted

Brief description :

Analyse :

#include 
#include 
#include 

using namespace std;
const int N = 1000;
const int MaxH = 1000;
int A[N];
int a, b, p;



struct HashTable{
	int index[MaxH], head[MaxH], next[MaxH], sz;
	int key[MaxH];
	
	inline void clear() {
		sz = 0;
		memset(head, -1, sizeof(head));
	}
	inline void insert(int id, int val) {
		int x = id % MaxH;
		index[sz] = id, key[sz] = val;
		next[sz] = head[x];
		head[x] = sz++;
	}
	inline int search(int id){
		int x = id % MaxH;
		for ( int it = head[x] ; it != -1 ; it = next[it] ) 
			if ( index[it] == id ) return key[it];
		return -1;
	}
} hash;



inline int _M(int a){
	if (a < 0) return a + p;
	return a;
}

inline int _I(int b){
	int a = p;
	int x1 = 0, x2 = 1, q;
	while (true){
		q = a / b, a %= b;
		if (!a) return _M(x2);
		x1 -= q * x2;
		q = b / a, b %= a;
		if (!b) return _M(x1);
		x2 -= q * x1;
	}
}

int Dlog(){

	// Baby-Step ...
	int m = ceil(sqrt(p)); //??
	
	A[0] = 1;
	for (int i=1;i<=m;i++){
		A[i] = (A[i-1] * a) % p;
		if (A[i] == b) return i;
	}
	
	hash.clear();
	for (int i=0;i> a >> b >> p){
		cout << Dlog() << endl;
	}
}

/*
 p 素数. ..
 
 a, p 互素

 a, p 不互素
*/

External link :

    https://www.spoj.pl/problems/MOD/