阶乘[分解质因数][二分答案]

阶乘[分解质因数][二分答案]

描述

有n个正整数a[i]，设它们乘积为p，你可以给p乘上一个正整数q，使p*q刚好为正整数m的阶乘，求m的最小值。

输入

共两行。

第一行一个正整数n。

第二行n个正整数a[i]。

输出

共一行

一个正整数m。

样例输入

1 6

样例输出

3

提示

样例解释：

当p=6，q=1时，p*q=3！

【数据范围与约定】

对于10%的数据，n<=10

对于30%的数据，n<=1000

对于100%的数据，n<=100000，a[i]<=100000

先看一个简单的问题： 27！里面有多少个 3 相乘？ 27！=1*2*...*27 包含 1 个 3 的数有 27/(3^1)=9 个 包含 2 个 3 的数有 27/(3^2)=3 个 包含 3 个 3 的数有 27/(3^3)=1 个 总共：9+3+1=13 个 所以 27！里面有 13 个 3 相乘。 用这个方法就可以求得 m！有多少个 ai 相乘，二分判断即可

#include#define N 100005#define Mod 1000003#define LL long long using namespace std;int read(){ int cnt=0;char ch=0; while(!isdigit(ch))ch=getchar(); while(isdigit(ch))cnt=cnt*10+(ch-'0'),ch=getchar(); return cnt; } int n,vis[N],Max; bool check(int m){ if(m>1; if(check(mid)) r=mid; else l=mid+1; }printf("%d",l); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。