原题大意

给出两个数a, b,问有多少i使得i!能被a整除，而不能被b整除。

算法分析

对于一个数字n，如果x!是可以被它整除的第一个数，那么x之后的数都能整除。
将x计作 f（n），答案就是max(0, f(b)-f(a))。
对于f的计算，就是对于n分解质因数，然后对于每一个因数算出要满足这个因数所需要的x，取max即为f。

程序代码

#include <bits/stdc++.h>
#define mem(a,b) memset(a, b, sizeof(a))
using namespace std;
typedef long long ll;
int a, b;

//得到能被x^cnt整除的最小阶乘n！，n一定是x的整数倍。
int get(int x, int cnt){
    int t = 1;
    //如果能将cnt个x整除完
    while(cnt){
        int tmp = t*x;
        while(tmp % x == 0 && cnt){
            tmp/=x;
            cnt--;
        }
        if(cnt) t++;
    }
    return t * x;
}
int cal(int n){
    int ans = 1, tmp = n;
    //质因数分解
    for(int i = 2; i * i <= n; i++){
       if(tmp%i==0)
        {
            int cnt = 0;
            while(tmp%i==0) tmp/=i, cnt++;
            ans = max(ans, get(i,cnt));
        }
    }
    //若n本身是质数,阶乘必然从n开始
    if(tmp > 1) ans = max(ans, tmp);
    return ans;
}
int main(){
freopen("input.txt", "r", stdin);
    ios::sync_with_stdio(false);
    cin.tie(0);cout.tie(0);
    cin >> a >> b;
    cout << max(cal(b) - cal(a), 0) << endl;
    return 0;
}