【BZOJ4522】密匙破解（Pollard_rho）

题面

BZOJ

洛谷

题解

还是\(Pollard\_rho\)的模板题。

呜。。。

#include<iostream>

#include<cstdio>

#include<cstdlib>

#include<cstring>

#include<cmath>

#include<algorithm>

#include<set>

#include<map>

#include<vector>

#include<queue>

using namespace std;

#define ll long long

#define RG register

inline ll read()

{

    RG ll x=0,t=1;RG char ch=getchar();

    while((ch<'0'||ch>'9')&&ch!='-')ch=getchar();

    if(ch=='-')t=-1,ch=getchar();

    while(ch<='9'&&ch>='0')x=x*10+ch-48,ch=getchar();

    return x*t;

}

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

ll Multi(ll a,ll b,ll MOD)

{

	ll s=0;

	while(b){if(b&1)s=(s+a)%MOD;a=(a+a)%MOD;b>>=1;}

	return s;

}

ll fpow(ll a,ll b,ll MOD)

{

	ll s=1;

	while(b){if(b&1)s=Multi(s,a,MOD);a=Multi(a,a,MOD);b>>=1;}

	return s;

}

bool Miller_Rabin(ll x)

{

	if(x==2)return true;

	for(int tim=10;tim;--tim)

	{

		ll a=rand()%(x-2)+2;

		if(fpow(a,x-1,x)!=1)return false;

		ll p=x-1;

		while(!(p&1))

		{

			p>>=1;ll nw=fpow(a,p,x);

			if(Multi(nw,nw,x)==1&&nw!=1&&nw!=x-1)return false;

		}

	}

	return true;

}

ll Pollard_rho(ll n,int c)

{

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

	while(233)

	{

		++i;x=(Multi(x,x,n)+c)%n;

		ll d=__gcd((y+n-x)%n,n);

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

		if(x==y)return n;

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

	}

}

vector<ll> fac;

void Fact(ll n,int c)

{

	if(n==1)return;

	if(Miller_Rabin(n)){fac.push_back(n);return;}

	ll p=n;while(p>=n)p=Pollard_rho(p,c--);

	Fact(p,c);Fact(n/p,c);

}

void exgcd(ll a,ll b,ll &x,ll &y)

{

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

	exgcd(b,a%b,y,x);

	y-=Multi(a/b,x,r);y=(y%r+r)%r;

}

ll Inv(ll a,ll b)

{

	ll x,y;exgcd(a,b,x,y);

	x=(x%b+b)%b;return x;

}

int main()

{

	e=read();N=read();c=read();Fact(N,233);

	r=(fac[0]-1)*(fac[1]-1);

	d=Inv(e,r);

	n=fpow(c,d,N);

	printf("%lld %lld\n",d,n);

	return 0;

}