一道Pollard Rho模板题。
#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<ctime>
#include<algorithm>
#define gc getchar()
#define ll long long
#define ld long double
#define ull unsigned long long
using namespace std;
const int N=1e5+5,M=8555;
ll a[20]={2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 61, 24251, 2147483647, 998244353};
ll inf=1ll<<62;
template<class o>
inline void qr(o &x)
{
x=0;char c=gc;int f=1;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
template<class o>
void qw(o x)
{
if(x<0)putchar('-'),x=-x;
if(x/10)qw(x/10);
putchar(x%10+48);
}
inline ll mul(ll a,ll b,ll p)
{
ll x=(ld)a/p*b;
ll c=1ull*a*b-1ull*x*p;
return (c+p)%p;
}
inline ll fpow(ll a,ll b,ll p){ll ans=1;for(;b;b>>=1,a=mul(a,a,p))if(b&1)ans=mul(ans,a,p);return ans;}
ll gcd(ll a,ll b){return b?gcd(b,a%b):a;}
ll exgcd(ll a,ll b,ll &x,ll &y){if(!b){x=1;y=0;return a;}ll d=exgcd(b,a%b,y,x);y-=(a/b)*x;return d;}
ll f(ll x,ll c,ll n){return (mul(x,x,n)+c)%n;}
ll pr(ll n)
{
ll s=0,t=0,c=rand()%(n-1)+1,val=1;
for(int i=1;;i<<=1,s=t,val=1)
{
for(int j=1;j<=i;j++)
{
t=f(t,c,n);
val=mul(val,abs(t-s),n);
if(j%127==0)
{
ll d=gcd(val,n);
if(d>1)return d;
}
}
ll d=gcd(val,n);
if(d>1)return d;
}
}
int main()
{
ll e,n,c;qr(e),qr(n),qr(c);
ll p=n;while(p>=n)p=pr(n);
ll q=n/p,r=(p-1)*(q-1);
ll x,y,d;d=exgcd(e,r,x,y);
x=(x%r+r)%r;qw(x);putchar(' ');
ll w=fpow(c,x,n);
qw(w);puts("");
return 0;
}
最后一次更新于2020-03-28
0 条评论