对lyd书上的一点补充

大体思路通lyd书上解法2

但是书上有一句原话是“若d不能被上述任何数整除，则d为质数，计算$cnt_{d}$”

实际上d可能是某个大质数的倍数，它同样也被小质数整除了。所以计算的时候要边分解边缩小d，最后如果d > 1那么d就是大质数的一个倍数，再对其进行分解

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1e6 + 233;
typedef long long ll;
ll n, a0, a1, b0, b1, ans;
ll primes[maxn], cnt ;
bool st[maxn];
void get_primes(ll n)
{
    for(ll i = 2; i <= n; i++)
    {
        if(!st[i]) primes[cnt++] = i;
        for(int j = 0; j < cnt && i * primes[j] <= n; j++)
        {
            st[i * primes[j]] = 1;
            if(i % primes[j] == 0) break;
        }
    }
}
ll get(ll &x, ll &y)
{
    ll res = 0;
    //cout<<"---"<<x%y<<endl;
    while(x % y == 0)
    {
        x /= y;
        res++;
    }
    return res;
}
int solve(ll p)
{

    if(p > b1) return 0;
    if(b1 % p != 0) return 1;
    ll cntp = 0;
    ll numa0 = get(a0, p); 
    ll numa1 = get(a1, p); 
    ll numb0 = get(b0, p); 
    ll numb1 = get(b1, p); 
    if(numa1 < numa0 && numb0 < numb1 && numa1 == numb1) cntp = 1;
    else if(numa1 < numa0 && numb0 == numb1 && numa1 <= numb1) cntp = 1;
    else if(numa1 == numa0 && numb0 < numb1 && numa1 <= numb1) cntp = 1;
    else if(numa1 == numa0 && numb0 == numb1 && numa1 <= numb1) cntp = numb1 - numa1 + 1;
    else cntp = 0;
    ans *= cntp;
    return 1;
}
int main()
{
    get_primes(100000);

    cin >> n;
    while(n--)
    {
        cin >> a0 >> a1 >> b0 >> b1;
        ans = 1; bool flag = 1;
        for(int j = 0; j < cnt; j++)
        {
            ll p = primes[j];
            if(solve(p)) continue;
            break;
        }
        if(b1 > 1) solve(b1);
        cout << ans << endl;
    }
}