hrbeu 1318 X ^ a mod b = c 2 차 남 음

모드 소수 p 의 원 근 g 의 아름다움 은 모든 모드 p 의 0 이 아 닌 g 의 속도 로 나타 나 는 것 에 나타난다.그래서, 모든 수 1 < = a < p, 우 리 는 멱 을 선택 할 수 있 습 니 다.
 　　　　　　　　g,g^2,g^2,```````,g^(p-2),g^(p-1)
마침 a 모드 p 와 같 습 니 다.해당 지 수 는 g 를 바탕 으로 하 는 a 모드 p 의 지표 라 고 불 린 다.p 와 g 가 지정 되 었 다 고 가정 하면 지 표를 I (a) 로 기록 합 니 다.
다음은 2 모 13 의 모든 멱 형식 으로:
I　　　　　　　   1　  2　　3　   4　  5　　 6　　 7　　 8　   9　　10　  11　12
2^I(mod 13)　  2　　4　　8　　3　　6　　12　　11　　9　　5　　10　　7　　1
예 를 들 어 I (11) 를 구하 기 위해 우 리 는 표 의 두 번 째 줄 을 찾 아서 11 을 찾 을 때 까지 지표 I (11) = 7 을 첫 줄 에서 얻 을 수 있다.
지표 법칙
　　a).　　I(ab)=I(a)+I(b) (mod p-1)
　　b).　　I(a^k)=kI(a) (mod p-1)
g^I(ab)=ab=g^I(a)g^I(b)=g^(I(a)+I(b)) (mod p)
그래서 g ^ I (x) = x (mod p - 1)
g ^ I (value) = id (mod p - 1)
예제: 3 * x ^ 30 = 4 (mod 37)
I(3*x^30)=I(4)
I(3)+30*I(x)=I(4) (mod 36)
26+30*I(x)=2 (mod 36)
30*I(x)=-24=12 (mod 36)
여기에 대해 I (4) = 2 설명:
사실은 g ^ 2 = 4 (mod 36)
사실 이 건 g ^ x = b (mod p) 에 따라 구 할 수 있어 요.
이 문제 에 대해 g 는 37 의 원근 2, b = I (x) p = 36 이다.
즉 2 ^ x = I (x) (mod 36) 의 x 를 만족 시 키 는 것 이다.Baby Step Giant Step 알고리즘 을 사용 하 시 면 됩 니 다. 
알림: 양쪽 을 6 으로 나 누 어 5 * I (x) + 2 (mod 36) 를 얻 지 마 십시오. 그렇지 않 으 면 해 를 잃 어 버 릴 수 있 습 니 다.
ax = c (mod m)
확장 유클리드 에서 알 수 있 습 니 다:
I(x)=4,10,16,22,28,34
마지막 으로 지표 표 (서 론 서 에 있 습 니 다. 프로그램 을 놓 지 않 고 보 세 요) 가 있어 x 의 대응 치 를 얻 을 수 있 습 니 다.
I(16)=4,I(25)=10,I(9)=16
 I(21)=22,I(12)=28,I(28)=34
사실 여기 서도 지표의 원 식 공식 g ^ I (x) = x (mod p - 1) 에 따라
그러므로 동 여 식 3 * x ^ 30 = 4 (mod 37) 는 6 개의 해 가 있다. 즉,
x=16,25,9,21,12,28 (mod 37)

/*

 * hrbeu1318.c

 *

 *  Created on: 2011-10-13

 *      Author: bjfuwangzhu

 */

#include<stdio.h>

#include<math.h>

#include<string.h>

#include<stdlib.h>

#define LL long long

#define nmax 4001

typedef struct num {

	int ii, value;

} num;

num Num[nmax];

int flag[nmax], prime[nmax], pfactor[nmax], cpfactor[nmax];

int plen, len_pfactor, k, n, p, proot, x, y;

void mkprime() {

	int i, j;

	memset(prime, -1, sizeof(prime));

	for (i = 2; i < nmax; i++) {

		if (prime[i]) {

			for (j = i + i; j < nmax; j += i) {

				prime[j] = 0;

			}

		}

	}

	for (i = 2, plen = 0; i < nmax; i++) {

		if (prime[i]) {

			prime[plen++] = i;

		}

	}

}



void findpFactor(int n) {

	int i, te, cnt;

	te = (int) sqrt(1.0 * n);

	for (i = 0, len_pfactor = 0; (i < plen) && (prime[i] <= te); i++) {

		if (n % prime[i] == 0) {

			cnt = 0;

			while (n % prime[i] == 0) {

				cnt++;

				n /= prime[i];

			}

			pfactor[len_pfactor] = prime[i];

			cpfactor[len_pfactor++] = cnt;

		}

	}

	if (n > 1) {

		pfactor[len_pfactor] = n;

		cpfactor[len_pfactor++] = 1;

	}

}

/*     a^b%c*/

int modular_exp(int a, int b, int c) {

	LL res, temp;

	res = 1 % c, temp = a % c;

	while (b) {

		if (b & 1) {

			res = res * temp % c;

		}

		temp = temp * temp % c;

		b >>= 1;

	}

	return (int) res;

}

int dfs(int depth, LL now) {

	int i;

	LL res, temp;

	if (depth == len_pfactor) {

		res = modular_exp(proot, now, p);

		if ((res == 1) && (now != (p - 1))) {

			return 0;

		}

		return 1;

	}

	for (i = 0, temp = 1; i <= cpfactor[depth]; i++) {

		if (!dfs(depth + 1, now * temp)) {

			return 0;

		}

		temp = temp * pfactor[depth];

	}

	return 1;

}

void primitive() {

	findpFactor(p - 1);

	for (proot = 2;; proot++) {

		if (dfs(0, 1)) {

			return;

		}

	}

}

int extend_gcd(int a, int b) {

	int d, xx;

	if (b == 0) {

		x = 1, y = 0;

		return a;

	}

	d = extend_gcd(b, a % b);

	xx = x;

	x = y, y = xx - a / b * y;

	return d;

}



int bfindNum(int key, int n) {

	int left, right, mid;

	left = 0, right = n;

	while (left <= right) {

		mid = (left + right) >> 1;

		if (Num[mid].value == key) {

			return Num[mid].ii;

		} else if (Num[mid].value > key) {

			right = mid - 1;

		} else {

			left = mid + 1;

		}

	}

	return -1;

}

int cmp(const void *a, const void *b) {

	num n = *(num *) a;

	num m = *(num *) b;

	return n.value - m.value;

}

/* a^x = b (mod c)*/

int baby_step_giant_step(int a, int b, int c) {

	int i, j, te, aa;

	LL temp, xx;

	te = (int) (sqrt(1.0 * c) + 0.5);

	for (i = 0, temp = 1 % c; i <= te; i++) {

		Num[i].ii = i;

		Num[i].value = (int) (temp);

		temp = temp * a % c;

	}

	aa = Num[te].value;

	qsort(Num, te + 1, sizeof(Num[0]), cmp);

	for (i = 0, temp = 1; i <= te; i++) {

		extend_gcd((int) (temp), c);

		xx = (LL) x;

		xx = xx * b;

		xx = xx % c + c;

		x = (int) (xx % c);

		j = bfindNum(x, te + 1);

		if (j != -1) {

			return i * te + j;

		}

		temp = temp * aa % c;

	}

	return -1;

}

int rcmp(const void *a, const void *b) {

	return *(int *) a - *(int *) b;

}

/* ax = b (mod c)*/

int result[nmax];

void solve(int a, int b, int c) {

	int i, d, cc;

	d = extend_gcd(a, c);

	if (b % d) {

		puts("No Solution!");

		return;

	}

	cc = c;

	b /= d, c /= d;

	result[0] = ((LL) x * b % c + c) % c;

	for (i = 1; i < d; i++) {

		result[i] = (result[i - 1] + c) % cc;

	}

	for (i = 0; i < d; i++) {

		result[i] = modular_exp(proot, result[i], p);

	}

	qsort(result, d, sizeof(result[0]), rcmp);

	for (i = 0; i < d; i++) {

		printf("%d
", result[i]);

	}

}

int main() {

#ifndef ONLINE_JUDGE

	freopen("data.in", "r", stdin);

#endif

	int a, b, c;

	mkprime();

	/*x^k = n (mod p) */

	while (~scanf("%d %d %d", &k, &p, &n)) {

		primitive();

		b = baby_step_giant_step(proot, n, p);

		a = k, c = p - 1;

		solve(a, b, c);

		printf("
");

	}

	return 0;

}