83D. Numbers(容斥+暴力)

传送门

由于不能包括的因子

所以得到的数字分解质因子后必定都是大于等于的质因子

那么一个数的质因子不会个...好像没什么用

搜索的复杂度是上天的。

那就套路的容斥,求符合条件的就是求符合条件的

那么如何求的方案数....

首先是倍数的数有个,在这基础上需要进行容斥,因为有数拥有比小的因子的同时也拥有

也就是减去是的倍数的数

这里使用递归计算

然后目测复杂度很低,因为一直除以

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a,b,k;
bool isprime(int x)
{
    for(int i=2;i*i<=x;i++)
        if( x%i==0 )    return false;
    return true;
}
int solve(int n,int k)
{
    if( n<k||!isprime(k) )    return 0ll;
    if( k*k>n )    return (n>=k);
    int ans = n/k;
    for(int i=2;i<k;i++)
        ans -= solve(n/k,i);
    return ans;
}
signed main()
{
    cin >> a >> b >> k;
    cout << solve(b,k)-solve(a-1,k) << endl;
    return 0;
}