题意：有N个ai，bi，M=a1^b1*a2^b2*a3^b3…*an^bn ,求最小的 x 使得 x! % M ==0.
思路：把M分成多个素数相乘，num[i] 记录素数 i 的个数，然后二分找到x，若 x! 中所有 i 的个数满足>=num[i]
即为答案。
#include #include #include #include #include #include #include #include #include #include #include using namespace std; #define INF 1e8 #define eps 1e-8 #define LL long long #define maxn 100105 #define mod 1000000009 int prime[25]={2,3,5,7,11,13,17,19,23,29,31, 37,41,43,47,53,59,61,67,71,73,79,83,89,97}; __int64 num[105]; void Cal(__int64 a,__int64 b)//计算素数i的个数num[i] { for(int i=0;i<25;i++) { while(a%prime[i]==0) { a/=prime[i]; num[prime[i]]+=b; } } } __int64 find(int i,__int64 x)//计算x!中i的个数 { __int64 ans=0; while(x) { x/=i; ans+=x; } return ans; } bool ok(__int64 x) { for(int i=0;i<25;i++) { if(num[prime[i]]) { __int64 tmp=find(prime[i],x); if(tmp >1; if(ok(mid)) { ans=mid; r=mid-1; } else l=mid+1; } printf("%I64d\n",ans); } return 0; }