這題問你有幾種進位法，使的$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; }
