洛谷10月月赛R1T1-SAC E#1 - 一道中档题 Factorial（pollard-rho质因数分解）

本文主要是介绍洛谷10月月赛R1T1-SAC E#1 - 一道中档题 Factorial（pollard-rho质因数分解），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

传送门
小数据做法（改了之后）：http://blog.csdn.net/stone41123/article/details/78172763
大数据做法（没改之前的数据范围）：
我们沿用之前的做法，只是质因数分解如果再用 $O(\sqrt n)$ 的，那么就会TLE
我们可以使用pollard-rho质因数分解，听说时间是 $O(n^{\frac 1 4})$ 的，我自己强化了数据跑了一下，0ms，快到飞起
代码：

#include<cstdio>
#include<cstring>
#include<iostream>
#include<cmath>
#include<algorithm>
#include<cstdlib>
#include<ctime>
#define ll long long
using namespace std;
typedef ll Tem;
inline Tem read(){Tem x=0;char ch=' ';int f=1;while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();if(ch=='-')f=-1,ch=getchar();while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();return x*f;
}
const int times=10;
inline ll mul(ll a,ll b,ll p){a%=p;b%=p;ll ans=0;while(b){if(b&1){ans=(ans+a)%p;}a=(a+a)%p;b>>=1;}return ans;
}
inline ll ksm(ll a,ll b,ll p){a%=p;ll ans=1;while(b){if(b&1){ans=mul(ans,a,p);}a=mul(a,a,p);b>>=1;}return ans;
}
inline bool miller_rabin(ll n){if(n==2)return true;if(n<2||(!(n&1)))return false;ll m=n-1;ll k=0;while(!(m&1)){m>>=1;k++;}for(int i=1;i<=times;i++){ll a=rand()%(n-1)+1;ll x=ksm(a,m,n);for(int j=1;j<=k;j++){ll y=mul(x,x,n);if(y==1&&x!=1&&x!=n-1)return false;x=y;}if(x!=1)return false;}return true;
}
inline ll gcd(ll a,ll b){if(a==0)return 1;if(a<0)return gcd(-a,b);ll t;while(b){t=a%b;a=b;b=t;}return a;
}
ll fac[10001],cnt;
inline ll pollard_rho(ll n,ll c){ll i=1,k=2;ll x0=rand()%(n-1)+1;ll y=x0;while(1){i++;x0=(mul(x0,x0,n)+c)%n;ll d=gcd((y-x0+n)%n,n);if(1<d&&d<n)return d;if(y==x0)return n;if(i==k){y=x0;k<<=1;}}
}
inline void findfac(ll n,ll c){if(n==1)return;if(miller_rabin(n)){fac[++cnt]=n;return;}ll p=n;ll cc=c;while(p>=n)p=pollard_rho(p,c--);findfac(p,cc);findfac(n/p,cc);
}
ll n,k,ans;
ll prime[10001],e[10001],tot;
int main(){n=read();k=read();findfac(k,23333);sort(fac+1,fac+cnt+1);for(int i=1;i<=cnt;i++){if(fac[i]==prime[tot]){e[tot]++;}else{e[++tot]=1;prime[tot]=fac[i];}}ans=100000000000000000LL;for(int i=1;i<=tot;i++){ll num=0,now=prime[i];if(now>n)break;while(now<=n){num+=n/now;now*=prime[i];}num/=e[i];ans=min(ans,num);}if(ans==100000000000000000LL)ans=0;printf("%lld",ans);return 0;
}