數字遊戲

幾個通信學院的同學問我的一道他們算法課程上的題，拿到還是想了一會兒才想出解題的方法，還是有點意思。

這題不是什麼高深的算法題，倒是有一點考驗思維，以及對進制存儲的了解，首先，在十進制下，後面的0的個數能用肉眼看出來，不難想到，我們一直把這個數除以10，直到不能再整除為止，除的次數就是後面跟着的0的個數。因為我們可以把這個數拆成a1*10^1+a2*10^2+……an*10^n，那麼前面有多少個ai是0，就在末尾有幾個0。

那麼我們再來延伸到b進制下，同樣把這數拆成a1*b^1+a2*b^2+……an*b^n，也是同樣的，前面有多少個ai是0，末尾就有幾個0，是以很簡單，隻要我們找到最小的an不為0的b^n，n就是末尾0的個數。

那麼問題就變成了這個數能整除b幾次，但是又有一個問題，n!會非常的大，就算long long 也隻有2^64(18位)是以我們不可能算出這個數再來除b。

是以我們還得進一步的轉換這個問題。當時想的是如果階層中這個數與b互質，我們就不用管它，它肯定和這個問題是沒有關系的，但是即使不互質的數乘起來，也會爆long long，是以這個問題還得再進一步被轉換。

既然不互質的也要爆，那麼此時自然而然的想到了把所有的數都分解成質因數的形式，我們把b分解成一些質因數乘積的形式b = p1^k1 * p2^k2 * ……* pn^kn，這個時候我們再對這個階層中出現的這些質因數進行統計，這一點因為不涉及到乘法，也不會爆，也相對容易。得到n! = p1^l1 * p2^l2 * ……* pn^ln之後，我們的問題相當于就變成了看l1,l2……ln，裡面有多少個k1,k2……kn，是以很顯然答案就是min(li / ki)。

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long LL;
int prime[20],sum1[20],sum[2];
int main()
{
  int n,b;
  scanf("%d%d", &b, &n);
  int num = 0,pn = 0,tmp = b;
  for(int i=2; i*i<=tmp; i++)
  {
    if(tmp%i == 0) prime[pn++] = i;
    while(tmp%i==0)
    {
      sum1[pn-1]++;
      tmp /= i;
    }
  }
  if(tmp > 1) prime[pn++] = tmp,sum1[pn-1]++;
  for(int i=2; i<=n; i++)
  {
    tmp = i;
    for(int j=0; j<pn; j++)
    {
      while(tmp%prime[j] == 0)
      {
        sum[j]++;
        tmp /= prime[j];
      }
    }
  }
  int Min = 1000000000;
  for(int i=0; i<pn; i++)
    Min = min(Min, sum[i]/sum1[i]);
  printf("%d\n", Min);
}