分析
题意就是(sum_{i=l}^r[k|i]*[mn[frac{i}{k}]geq k])
首先线性筛每个数的最小质因数，如果(frac{r}{k})较小直接暴力
否则(k)一定比较小，那么直接容斥解决即可
代码
#include <cstdio>
#include <cctype>
#include <algorithm>
#define rr register
using namespace std;
const int N=5000000;
int prime[N+101],v[N+101],cnt,Tot,ans,nn;
inline signed iut(){
rr int ans=0; rr char c=getchar();
while (!isdigit(c)) c=getchar();
while (isdigit(c)) ans=(ans<<3)+(ans<<1)+(c^48),c=getchar();
return ans;
}
inline void pro(){
for (rr int i=2;i<=N;++i){
if (!v[i]) v[i]=prime[++cnt]=i;
for (rr int j=1;j<=cnt&&prime[j]<=N/i;++j){
v[i*prime[j]]=prime[j];
if (i%prime[j]==0) break;
}
}
}
inline bool Is_Prime(int k){
if (k<=N) return v[k]==k;
for (rr int i=1;i<=cnt;++i){
if (prime[i]>k/prime[i]) break;
if (k%prime[i]==0) return 0;
}
return 1;
}
inline signed brute(int n,int k){
ans=1;
for (rr int i=2;i<=n;++i) ans+=v[i]>=k;
return ans;
}
inline void dfs(int dep,int now,int op){
if (dep>Tot){
ans+=op*(nn/now);
return;
}
dfs(dep+1,now,op);
if (now<=nn/prime[dep])
dfs(dep+1,now*prime[dep],-op);
}
inline signed Pro_DFS(int n,int k){
Tot=lower_bound(prime+1,prime+1+cnt,k)-prime-1,
ans=0,nn=n,dfs(1,1,1); return ans;
}
inline signed answ(int n,int k){
if (n<k||!Is_Prime(k)) return 0;
if (n/k<=N) return brute(n/k,k);
else return Pro_DFS(n/k,k);
}
signed main(){
rr int l=iut(),r=iut(),k=iut(); pro();
return !printf("%d",answ(r,k)-answ(l-1,k));
}