[UVa 11802]All Your Bases Belong to Us

題目連結

這題問你有幾種進位法，使的$N!$後面有$K$個$0$

假設你已經知道十進位的時候要怎麼算後面幾個$0$
可以發現，當要計算$B$進位時
我們可以先把$B$質因數分解
假設$B$分解後變成$2^{p_{1}}*3^{p_{2}}*5^{p_{3}}*7^{p_{4}}*...$
$N!$分解後變成$2^{q_{1}}*3^{q_{2}}*5^{q_{3}}*7^{q_{4}}*...$
(每個$q_{i}$可在$O(\log N)$的時間內算出來)

那麼$B$進位時$N!$就有$\min_{i=1}^{\infty}\left\lfloor\frac{q_{i}}{p_{i}}\right\rfloor$個$0$了
別被那個$\infty$嚇到，因為$i$到一個數字以後$p_{i}$就全部都是$0$了，也就是可以忽略

現在題目給你$N$和$K$，問你有幾種$B$
也就是有幾種$B$讓$\min_{i=1}^{\infty}\left\lfloor\frac{q_{i}}{p_{i}}\right\rfloor=K$

可以發現，每一項$\left\lfloor\frac{q_{i}}{p_{i}}\right\rfloor$都有一個下限$K$，但又不能全部$>K$
換句話說，就是至少要有一個$\left\lfloor\frac{q_{i}}{p_{i}}\right\rfloor=K$，其他的可以是$\geq K$的隨意值

我們可以使用排容原理
算出讓每個$\left\lfloor\frac{q_{i}}{p_{i}}\right\rfloor$都$\geq K$的$B$有幾種
再減掉讓每個$\left\lfloor\frac{q_{i}}{p_{i}}\right\rfloor$都$>K$的$B$有幾種

可以發現每個$\left\lfloor\frac{q_{i}}{p_{i}}\right\rfloor$都是獨立的 (想一想，為甚麼XD)
因此將每個$\left\lfloor\frac{q_{i}}{p_{i}}\right\rfloor$的合法情況數量乘起來就好 (別忘了$mod$一下)

合法情況數量怎麼算呢？
可以發現$q_{i}$是固定的，我們只需調整$p_{i}$即可
讓$\left\lfloor\frac{q_{i}}{p_{i}}\right\rfloor\geq K$的最大$p_{i}$就是$\left\lfloor\frac{q_{i}}{K}\right\rfloor$
讓$\left\lfloor\frac{q_{i}}{p_{i}}\right\rfloor>K$的最大$p_{i}$就是$\left\lfloor\frac{q_{i}}{K+1}\right\rfloor$

答案就是$\prod_{i=1}^{\infty}(\left\lfloor\frac{q_{i}}{K}\right\rfloor+1)-\prod_{i=1}^{\infty}(\left\lfloor\frac{q_{i}}{K+1}\right\rfloor+1)$
一樣，別被那個$\infty$嚇到，只要發現$\left\lfloor\frac{q_{i}}{K}\right\rfloor=0$時直接跳出迴圈即可

這樣會不會超時啊......
題目保證$\frac{N}{K}<500$
因此當質因數枚舉到$\geq 502$時，$q_{i}=\sum_{k=1}^{\infty}\left\lfloor\frac{N}{502^{k}}\right\rfloor<\sum_{k=1}^{\infty}\frac{N}{502^{k}}=\frac{N}{502(1-\frac{1}{502})}=\frac{N}{501}<K$
於是$\left\lfloor\frac{q_{i}}{K}\right\rfloor$就$=0$了

時間複雜度：$O(Q*91\log N)$ ($\leq 500$的質數有$91$個)

code:

#include<cstdio>
#include<cassert>
#include<algorithm>
#include<vector>
#include<map>
using namespace std;
typedef long long LL;
const LL MOD=1e9+7;
LL N,K;
vector<LL>P;
int main()
{
//    freopen("in.txt","r",stdin);
    P.push_back(2LL),P.push_back(3LL);
    for(int i=2,j;;i++)
    {
        P.push_back(P[i-1]);
        do
        {
            P[i]+=2LL;
            for(j=0;P[j]*P[j]<=P[i]&&P[i]%P[j]!=0LL;j++);
        }while(P[i]%P[j]==0LL);
        if(P[i]>=500LL)break;
    }
//    printf("%d\n",(int)P.size());
//    for(const LL &v:P)printf("%lld\n",v);
    int testcount;scanf("%d",&testcount);
    while(testcount--)
    {
        scanf("%lld%lld",&N,&K);
        LL ans1=1LL,ans2=1LL;
        for(int i=0;;i++)
        {
            assert(i<(int)P.size());
            LL power=0LL;
            {LL n=N;while(n)(power+=(n/=P[i]));}
            const LL &up=power/K,&down=power/(K+1LL);
            if(up==0LL)break;
            (ans1*=(up+1LL))%=MOD;
            (ans2*=(down+1LL))%=MOD;
        }
        static int kase=1;
        printf("Case %d: %lld\n",kase++,(ans1-ans2+MOD)%MOD);
    }
    return 0;
}