題目鏈接：點擊查看

題目大意：求k進制n的階乘下末尾0的個數

題目分析：之前接觸過10進制下求n的階乘末尾0的個數，當時只知道需要求5出現的個數，但并不知道原理，公式是這樣的：

int ans=0; while(n) {ans+=n/5;n/=5; }

也沒有去分析過原理，然后這道題目就要涉及到原理了，我們如果想要求末尾出現0，那么在k進制下就要盡可能多的出現k的冪，也就是k*k*……*k，讓其中的k的數量盡可能多，那么我們需要對k進行唯一分解，求出所有因子，然后對于每個因子都進行上述公式嘗試求結果，求出來的結果代表的是當前因子對于求盡可能多的k所做的貢獻，因為每個因子出現的次數不一定是一次，所以需要用這個結果再除以出現的次數，計算每個因子出現的頻率，最后選出最小值即可，證明的話我不太會證，所以很簡單的一道數論題不看別的大佬的思路真的做不出來。。

上代碼吧：

#include<iostream> #include<string> #include<cstring> #include<cstdio> #include<algorithm> #include<climits> #include<cmath> #include<cctype> #include<stack> #include<queue> #include<list> #include<vector> #include<set> #include<map> #include<unordered_map> using namespace std;typedef long long LL;const int inf=0x3f3f3f3f;const int N=1e6+100;bool book[N];int pri[N];int cnt=0;unordered_map<int,int>mp;void P()//歐拉篩 {for(int i=2;i<N;i++){if(!book[i])pri[cnt++]=i;for(int j=0;j<cnt&&pri[j]*i<N;j++){book[pri[j]*i]=true;if(i%pri[j]==0)break;}} }LL getnum(LL a,LL b)//求該質因子a在b中做出的貢獻 {LL ans=0;while(b){ans+=b/a;b/=a;}return ans; }int main() {P();LL n,k;cin>>n>>k;for(int i=0;i<cnt&&pri[i]<=sqrt(double(k));i++)//對k唯一分解 {while(k%pri[i]==0){k/=pri[i];mp[pri[i]]++;//mp維護每個質因子出現的次數}if(k==1)break;}LL ans=1e18;if(k!=1)//如果最后k還不為1，說明k為一個很大的質數，特判一下ans=min(ans,getnum(k,n));for(auto it:mp)//it.first代表質因子，it.second代表質因子出現的次數{ans=min(ans,getnum(it.first,n)/it.second);}cout<<ans<<endl;return 0; }

?

總結

以上是生活随笔為你收集整理的中石油训练赛 - 小A进学校(唯一分解定理)的全部內容，希望文章能夠幫你解決所遇到的問題。

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