C中的Codechef因子解決方案如何工作？

我想了解此代碼：C中的Codechef因子解決方案如何工作？

#include<stdio.h> 
int main() 
{ 
    int j,p,k; 
    long long int n,i; 
    scanf("%lld",&n); 
    for(k=n;k>=1;k--) 
     { 
      p=0; 
      scanf("%lld",&i); 
      for (j=5;j<=i;j*=5) 
      { 
       p=p+i/j; 
      } 
      printf("%d\n",p); 
     } 
    return 0; 
}

解決了這個問題Codechef：http://www.codechef.com/problems/FCTRL

什麼我有麻煩理解是這樣的循環是如何工作的：

for (j=5;j<=i;j*=5) 
      { 
       p=p+i/j; 
      }

爲什麼是j變量設置爲5，如果我將60的值給予i變量？

非常感謝！

來源

2014-03-19 user64437

@lundin我很好奇，爲什麼回滾？通常不鼓勵[在標題中重複標籤]（http://meta.stackexchange.com/questions/19190/should-questions-include-tags-in-their-titles），並對[在問題中稱呼]（ http://meta.stackexchange.com/questions/2950/should-hi-thanks-taglines-and-salutations-be-removed-from-posts）。另一個編輯是澄清哪些是改善職位。 –

@ShafikYaghmour您編輯了標題，使其沒有意義，然後添加了自己的文本。兩者都是無效的編輯。此外，編輯只是爲了刪除標題中的標籤，這是一個小小的改變，並沒有顯着改善帖子，正如編輯刪除「謝謝」一樣。「謝謝」不是一種稱呼。禮貌並沒有什麼不妥之處，因此SO不會阻止它（而不是增加簽名，這是不鼓勵的）。 – Lundin

@Lundin我在標題中做了太多錯誤，但是從閱讀這個問題來看不清楚代碼的目標是什麼，這很重要。如果這條鏈路在以後不再工作，這個問題就沒有多大意義。我添加的meta post似乎包括所有的致謝w/o區別，但我沒有做廣泛的搜索。 –

這段代碼：

p=0; 
scanf("%lld",&i); 
for (j=5;j<=i;j*=5) 
{ 
    p=p+i/j; 
}

計數在[1, i]和結果存儲在p所有整數因子5的數量。

循環1：j=5，p+=i/5計數數字，在範圍是整除5[1, i]
循環2：j=25，p+=i/25計數數字，是整除25範圍[1, i]（注意，這些數字已已經在循環中計數一次）
循環3：j=125, p+=i/125計數可被125整除的數字，範圍在[1, i]（請注意，這些數字已經存在在循環1和2）
....

來源

2014-03-19 11:45:09 starrify

總之問題計數兩次是找到一些1之間1000000000階乘的零的數目。
現在拿一支鉛筆和一張紙。從1開始。從1到4沒有0。第一個0發生在5!。接下來是10!，然後是15!, 20!, .....。這意味着零點的數量以5的間隔增加。

來到環

for (j=5;j<=i;j*=5) 
{ 
     p=p+i/j; 
}

見i是代表N這裏（見問題）。由於零的數量在5的間隔處增加，所以j被初始化爲5並且j將以5的倍數遞增。

現在簡單的規則是：在N!十進制表示尾隨零的數量僅僅是首要因素5的N!多樣性。

在聲明p=p+i/j;中，遵循相同的規則。程序的作者遞增j5直到N/j >= 5離開N（即i）在這裏。

N = i = 30 
p = 30/5 + 30/(5*5) = 6 // 30/25 is 1 and does not satisfying the condition N/j >= 5

來源

2014-03-19 11:45:29 haccks

在閱讀解釋之後，我得到我們需要找到5的倍數直到問題中的數字，但是，樣本輸入3的輸出爲14（如codechef網站中給出的）。你能解釋一下我的計算結果嗎？ –

@Subhasish我沒有得到你的問題。 – haccks

這裏[鏈接]（https://www.codechef.com/problems/FCTRL），請參閱示例部分。在示例輸入3中，輸出是14.我沒有得到它的14，我相信我錯過了一些東西，不知道是什麼。 –

這個算法更有意義，如果你瞭解他們使用的是找到它在Trailing zero Factorial和概述了階乘的尾隨零的數量的方法。基本上依靠洞察力，你需要考慮因子擴展中的所有5和2的產品，以發現最終會有多少個零。

的算法發現在x!尾隨零的數量歸結於：

發現的5
的結果除以x連續權力截斷結果添加到總
停止當除法結果小於1或在這個特定情況下，我們知道當結果大於x

所以，如果回去，我們可以發現以下步驟的代碼：

  step 3 
     | step 1 
     V V 
for (j=5;j<=i;j*=5) 
{ 
    p=p+i/j; // step 2 
}

來源

2014-03-19 11:52:57

C中的Codechef因子解決方案如何工作？

回答

相關問題