(找到最大的整数k使得n! % s^k ==0) (求n!在b进制下末尾0的个数) （区间满足个数）

题目：https://codeforces.com/contest/1114/problem/C

将b分解为若干素数乘积，记录每个素数含多少次方 b = p1^y1·p2^y2·...·pm^ym.

然后求n!种每个素数含多少次方n ! = p1^x1·p2^x2·...·pm^xm·

答案就是

#include<cstdio>
#include<iostream>
#include<algorithm>
#include<string>
#include<cstring>
#include<queue>
#include<stack>
#include<map>
#include<set>
#include<cmath>
#include<sstream>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const ll inf=0x3f3f3f3f;
ll n,b,res=1e18;
void solve(ll x,ll num){  //每个质因子  拥有的数量
    ll tp=1,ans=0;
    while(tp<=n/x){ //不能用tp*x会爆精度，有多少个x，就是先看有多少个x，再x^2,x^3,直到>n
        tp*=x;
        ans+=n/tp;
    }
    res=min(res,ans/num);
}
int main(){
    std::ios::sync_with_stdio(0);
    cin>>n>>b;
    ll t=b;
    for(ll i=2;i*i<=t;++i){ //分解质因子
        if(t%i==0){
            ll num=0;
            while(t%i==0){
                t/=i;
                num++;
            }
            solve(i,num); 
        }
    }
    if(t>1)    solve(t,1);
    cout<<res<<endl;
    return 0;
} 

十进制范围 [l,r] 内有多少整数满足在 k 进制下末尾恰好有 m 个 0

题目：https://acm.ecnu.edu.cn/contest/140/problem/D/

如果一个数的m进制后有k个零，就一定能被m^k  整除，而在含k个零中，一定存在含k+1个零的（含k+1个零就意味着一定含k个零），在1，2，3....x中，能被m^k  整除的有⌊x/m^k⌋个，所以只含k个零的个数有ans_x = ⌊x/m^k⌋-⌊x/m^k+1⌋，区间的话就是ans_r - ans_l-1 注意是l-1

#include<bits/stdc++.h>
using namespace std ;
#define ll long long
int main()
{
    int T;
    scanf("%d",&T);
    while(T--)
    {
        ll l,r;int k,m;
        scanf("%lld%lld%d%d",&l,&r,&k,&m);
        l--;

        while(m--)
        {
            r/=k;
            l/=k;
        }
        ll ans1=l-l/k,ans2=r-r/k;
        printf("%lld
",ans2-ans1);
    }
}