前言

比賽時xjq說這道題很水，是個基礎數論。
然后…
就連交都沒交

---

正題

給出n個數，求一個最小的$m$使得
$$\frac{m!}{{\prod }_{i=1}^n{a}_i}=q(q\in N_{+})$$

---

解題思路

我們考慮因為要求在一起的乘積，所以個體是不會單獨被處理的，所以我們可以將$a_{1～n}$的乘積分解質因數，然后如果$m!$能夠將所有的這些質因子都消掉就可以了。
然后我們考慮單獨的一個質因子，比如：
a的乘積有2個5
我們發現$5!$只有1個5
但是$10!$有2個5，可以消掉，所以這個m至少要求是10。

這樣我們就可以得出算法，將a的乘積分解質因數，然后對于每個質因子求一個最小的$m$，然后取這些要求中的最大值就好了。

---

code

#include<cstdio> #include<algorithm> #define N 100010 using namespace std; int n,a,p[N],m,ans; int main() {scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d",&a);for(int j=2;j*j<=a;j++)while(!(a%j))p[j]++,a/=j,ans++;if(a>1) p[a]++,ans++;}//分解乘積for(int i=2;i<=N-10;i++)if(p[i]){int cur=i;while(p[i]){int tmp=cur;while(p[i]&&!(tmp%i)) p[i]--,tmp/=i;cur+=i;}//求最小m的要求m=max(m,cur-i);//取最大要求}printf("%d",m); }

總結

以上是生活随笔為你收集整理的nssl1174-阶乘【!基础!数论】的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。