CODE

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;

queue<int>arr;

inline LL multi(LL a, LL b, LL p) { //快速乘

	LL re = a * b - (LL)((long double) a / p * b + 1e-8) * p;

	return re < 0 ? re + p : re;

}

LL gcd(LL a, LL b) { return b ? gcd(b, a%b) : a; }

inline LL qpow(LL a, LL b, LL p) {

	LL re = 1;

	while(b) {

		if(b&1) re = multi(re, a, p);

		a = multi(a, a, p); b >>= 1;

	}

	return re;

}

inline LL Pollard_Rho(LL n, int sed) {

	LL i = 1, k = 2, x = rand()%(n-1)+1, y = x;

	while(true) {

		x = (multi(x, x, n) + sed) % n;

		LL p = gcd(n, (y-x+n)%n);

		if(p != 1 && p != n) return p;

		if(y == x) return n;

		if(++i == k) y = x, k <<= 1;

	}

}

LL x[100];

inline bool MR(LL n) {

	if(n == 2) return 1;

	int s = 20, t = 0; LL u = n-1;

	while(!(u&1)) ++t, u>>=1;

	while(s--) {

		LL a = rand()%(n-2) + 2;

		x[0] = qpow(a, u, n);

		for(int i = 1; i <= t; ++i) {

			x[i] = multi(x[i-1], x[i-1], n);

			if(x[i] == 1 && x[i-1] != 1 && x[i-1] != n-1) return 0;

		}

		if(x[t] != 1) return 0;

	}

	return 1;

}

void find(LL n, int sed) {

	if(n == 1) return;

	if(MR(n)) { arr.push(n); return; }

	LL p = n; int k = sed;

	while(p == n) p = Pollard_Rho(p, sed--);

	find(p, k);

	find(n/p, k);

}

LL p, q, e, d, N, c, tmp, Z;

void exgcd(LL a, LL b, LL &x, LL &y, LL &Z) {

	if(!b) { x = 1; y = 0; Z = a; return; }

	exgcd(b, a%b, y, x, Z); y -= x*(a/b);

}

int main()

{

	srand(19260817);

	scanf("%lld%lld%lld", &e, &N, &c);

	find(N, 107);

	p = arr.front(), arr.pop();

	q = arr.front(), arr.pop();

	exgcd(e, (p-1)*(q-1), d, tmp, Z);

	Z = (p-1)*(q-1)/Z;

	d = (d % Z + Z) % Z;

	printf("%lld %lld\n", d, qpow(c, d, N));

}
巴特西

BZOJ 4522: [Cqoi2016]密钥破解 (Pollard-Rho板题)

CODE

最新文章

热门文章
