Tag: 慢速乘

题目传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=4522
数据生成器：http://paste.ubuntu.com/23140343/

这题，我觉得唯一的难点在分解因数
因为忘了棒棒糖怎么写，于是考试的时候只能写了50分的暴力
话说CQOI怎么能考模板呢？

#include<bits/stdc++.h>
#define LL long long
#define abs(x) ((x)>0?(x):-(x))
using namespace std;

LL e,N,c,r,d,n; 

void EX_GCD(LL &x, LL a, LL &y, LL b) {
	if (!b) {x = 1; y = 0;}
	else {EX_GCD(y,b,x,a%b); y -= a/b*x;}
}

inline LL EX_GCD(LL a, LL b) {
	LL t1, t2;
	EX_GCD(t1,a,t2,b);
	return (t1%r + r) % r;
}

inline LL Mul(LL a, LL b) {
	LL ret = 0;
	while (b) {
		if (b&1) ret  = (ret + a) % N;
		a = a*2 % N; b >>= 1;
	}
	return ret;
}

inline LL pow(LL w, LL t) {
	LL ret = 1;
	while (t) {
		if (t & 1) ret = Mul(ret, w);
		w = Mul(w, w); t >>= 1;
	}
	return ret;
}

inline LL GCD(LL a, LL b){
	while (b) a = a % b, swap(a, b);
	return a;
}

inline void Decompose(){
	for (int seed=(rand()&32767)%(N-1)+1;!r;seed=(rand()&32767)%(N-1)+1) {
		LL w = rand() % (N-1) + 1, seg=2, tmp = -1, cnt = 0, gcd;
		while (w != tmp && !r) {
			gcd = GCD(abs(w-tmp), N);
			if (1 < gcd && gcd < N) r = Mul(N/gcd-1,gcd-1); 
			if (++cnt == seg) seg <<= 1, tmp = w;
			w = (Mul(w,w) + seed) % (N-1) + 1;
		}
	}		
}

int main(){
	srand(999971); 
	cin>>e>>N>>c; Decompose(); 
	d = EX_GCD(e,r); n = pow(c,d);
	cout<<d<<' '<<n;
	return 0;
}