学步园

题目链接：点击打开链接

题目的意思很是简单：

n！在b进制下，末尾0为为k个的b有多少个。

先把n！的分解质因数。不需要全部的分解。因为n/k < 500。

比如说数据n=10，k=2；

10！=2^8*3^4*5^2*7=(2^4*3^2*5)^2*7；

那么末尾为2个的0的就靠(2^4*3^2*5)来进行组合了。

2^0---2^4;

3^0---3^2;

5^0---5^1;所有的组合就是5*4*2=30种。

我们知道里面一定有一些不符合的。

那么不符合是那些呢？

2^0---2^2

3^0---3^1

5^0;

是不符合。为什么？

因为2^8/2^0=2^7这样的话，就是末尾有7个0了。

其他同理。

那么不符合条件的就是，3*2*1=6种了。

答案：30-6=24；

代码：

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
#define LL __int64

const int N=505;
const LL mod=1e9+7;
int prime[N],top;

bool Judge(int x){
    int i,d=(int)sqrt(x);
    for(i=2;i<=d&&x%i!=0;i++);
    if(i>d) return true;
    else return false;
}

void get_prime(){
    int i;top=0;
    for(i=2;i<=500;i++){
        if(Judge(i))
        prime[top++]=i;
    }
    top=top-1;
}

LL f(LL n,LL m){
    if(n<m) return 0;
    else return n/m+f(n/m,m);
}

int main(){
    get_prime();
    LL n,k,T;
    scanf("%I64d",&T);
    while(T--&&scanf("%I64d%I64d",&n,&k)){
        int i;
        LL num1[N],ans1=1,ans2=1;
        memset(num1,0,sizeof(num1));
        for(i=0;i<=top;i++){
            num1[i]=f(n,prime[i]);
        }
        for(int i=0;i<=top;i++){
            if(num1[i]/k){
                int d=num1[i]/k,d1=0;
                ans1=(ans1*(d+1))%mod;
                for(int j=1;j<=d;j++)
                if(num1[i]/j!=k) d1++;
                else break;
                ans2=(ans2*(d1+1))%mod;
            }
        }
        printf("%I64d\n",((ans1-ans2)%mod+mod)%mod);
    }
    return 0;
}

最后一段：

((ans1-an2)%mod+mod)%mod;

在许多程序中，都看到过这一句话。

今天终于知道为什么咯！

因为ans1，和ans2都是mod后的，就是有可能ans1<ans2。所以要这么处理一下。