首先讲一下哦,这是一个神奇的算法,所以比较不太好理解(我是菜到交了几十次过了之后才懂得QQwQ)
作为一个优秀的随机算法,复杂度什么的完全不好分析啊(其实是俺懒得分析了……
都说了它是随机算法了,那么我们先随机暴力一波:
while(1) { int x=rand()%(n-1)+1; if(!(n%x) ans[++sum]=x; }
emmmm,确实暴力的一点,你要是这样都过了,就去买彩票吧……
不过这样给我们提供了一种思路,就是我们让随机出来的东西尽量接近的因子。
先来看一个这个好东西:
生日悖论
我们有个数,我们现在要在他们中间找到一个$s$,概率是$\frac{1}{n}$吧。
稍微改一下,我们找到两个数使他们差为$s$,概率是$\frac{2}{n}$呢。(唉,为啥啊?)
让我们看看郭队怎讲:
我们想一下哦,先找$t$的概率为$1$,再找一个和他的差为$s$的选择有两个:$s-t$和$s+t$
所以说啊,概率就是概率是$\frac{1}{n}$。
是不是豁然开朗了?那么我们选个呢$K$?
概率就会变成大哦。($Eg: n=1000,k=100$时基本接近完全成功)
让我们拓展到生日上,假设我们找一个人生日为$3.21$,概率是$\frac{1}{365}$。
在这相当于我们在$[1,365]$中随机选取一个数,该数为$90$的概率是多少?
回到了一开始的问题上,这样我们就可以套用了,据此我们可以推出$K=58$时近乎成功(网上有相应的代码,自己找!)
然而,我们当了这么多年学生也没找的这样的人QAQ,因而称此为悖论。
$\huge{Pollard-Rho}$
所以我们只要弄出一个数列,在他们中询问有无$x-y$可以整除$n$的数(好像概率也不大啊……)
不妨再改进一下,求$gcd(x-y,n)>1$的值,这样不就好多了么QQwQ。
考虑如何构造数列,这里有一个半随机的方式:$f(x)=(x^2+a)modN$。
依此来生成数列,会有一个问题出现,就是因为他有一个固定的生成方式,就有可能生成一个环:
(大概长这样……好像有点丑……)
所以它叫Pollard-Rho~(≧▽≦)/~啦。
好吧,我们来看看怎么去环,很简单,让$x$和$y$同时开始,$x$为$y$的两倍速即可。当$x==y$时就有一个环出现,就可以弹出了。
上代码:
#include<bits/stdc++.h> using namespace std; #define int __int128 inline int read() { int f=1,w=0;char x=0; while(x<'0'||x>'9') {if(x=='-') f=-1; x=getchar();} while(x!=EOF&&x>='0'&&x<='9') {w=(w<<3)+(w<<1)+(x^48);x=getchar();} return w*f; } int e,N,c,p,r,d; inline void exgcd(int a,int b,int &x,int &y) { if(!b) {x=1,y=0;return ;} exgcd(b,a%b,y,x); y=(r+y-a/b*x%r)%r; } int maxn; inline void print(__int128 x) { if(!x) {puts("0");return;} string ret=""; while(x) {ret+=x%10+'0'; x/=10;} reverse(ret.begin(),ret.end()); cout<<ret; } inline int gcd(int a,int b){ return b?gcd(b,a%b):a;} inline int ksm(int b,int p,int k) { int a=b; p--; while(p) { if(p%2) a=((b%k)*(a%k))%k; b=((b%k)*(b%k))%k; p/=2; } return a%k; } inline bool judge(int a,int n) { int now=n-1,c=0; while(!(now%2)) now/=2,c++; int las=ksm(a,now,n); if(las==1||las==n-1) return 1; while(c--) { las=((las%n)*(las%n))%n; if(las==n-1) return 1; } return 0; } inline bool Miller_Rabin(int n) { if(n==2||n==3) return 1; if(n<2||!(n%2)) return 0; for(int i=1;i<=4;i++) { int a=rand()%(n-1)+1; if(!judge(a,n)) return 0; } return 1; } int M=127; inline int abss(int x) {return x<0?-x:x;} inline int Pollard_Rho(int n,int c) { if(n%2==0) return 2; if(n%3==0) return 3; if(n%5==0) return 5; int d=1,x=0,y=0,z=1; for(int k=2;;k<<=1,y=x,z=1) { for(int i=1;i<=k;i++) { x=(((x%n)*(x%n))%n+c)%n; z=((z%n)*(abss(x-y)%n))%n; if(!(i%M)) { d=gcd(z,n); if(1<d) return d; } if(y==x) return n; } d=gcd(z,n); if(1<d) return d; } } int tmp; main(){ srand((unsigned)time(NULL)); e=read(),N=read(),c=read(),p=N; while(p>=N) p=Pollard_Rho(N,rand()%(N-1)+1); r=(p-1)*(N/p-1);exgcd(e,r,d,tmp); print(d);printf(" ");print(ksm(c,d,N)); }