题意：
给出l,r,k，(1 ≤ l ≤ r ≤ 2·10, 2 ≤ k ≤ 2·10)
求在区间[l,r]内有多少个数i满足 k | i,且[2,k-1]的所有数都不可以被i整除
首先，如果k不是素数的话，答案肯定是0
考虑k是素数：
fir[i]保存i的第一个素因子，fir[]可以在线性筛的时候得到
我们先把N以内的数线性筛出来
所以其实就是求：
[l,r]中满足fir[i] = k 的i的个数
[l,r] = [1,r] - [1,l-1]
所以现在我们要求的就是：
[1,r]中满足fir[i] = k 的i的个数，也就是
[1,r/k]中满足fir[i] >= k 或 i = 1的i的个数
n = r / k
如果n <N，直接遍历fir,统计fir[i] >= k || i == 1 的i的个数
如果n >= N,就相当于要把[1,n]中2的倍数，3的倍数，等小于k的素数的倍数筛去
dfs搜，容斥，考虑到2 * 3 * ... * 23 * 29 > 2 * 10^9，所以复杂度不会很大
这个套路也很喜闻乐见
代码：
//File Name: cf83D.cpp
//Created Time: 2017年01月04日 星期三 22时48分56秒 #include <bits/stdc++.h>
#define LL long long
using namespace std;
const int MAXN = + ;
bool check[MAXN];
int prime[],fir[MAXN],tot;
LL ans,n;
int ma;
void init(){
tot = ;
memset(check,false,sizeof(check));
for(int i=;i<MAXN;++i){
if(!check[i]){
prime[tot++] = i;
fir[i] = i;
}
for(int j=;j<tot;++j){
if((LL)i * prime[j] >= MAXN) break;
check[i * prime[j]] = true;
fir[i * prime[j]] = prime[j];
if(i % prime[j] == ) break;
}
}
// printf("tot = %d\n",tot);
}
bool is_prime(LL k){
if(k < MAXN)
return fir[k] == k;
for(int i=;i<tot;++i){
if(1LL * prime[i] * prime[i] > k) break;
if(k % prime[i] == ) return false;
}
return true;
}
void dfs(int p,LL now,LL f){
if(now > n) return ;
if(p > ma){
ans += f * (n / now);
return ;
}
dfs(p+,now,f);
dfs(p+,now * prime[p],-f);
}
LL cal(LL r,LL k){
ans = ;
n = r / k;
if(n < MAXN){
for(int i=;i<=n;++i){
if(i == || fir[i] >= k)
++ans;
}
return ans;
}
else{
ma = ;
for(;ma<tot;++ma){
if(prime[ma] == k)
break;
}
--ma;
dfs(,,);
return ans;
}
}
LL solve(LL l,LL r,LL k){
if(!is_prime(k)) return ;
return cal(r,k) - cal(l - ,k);
}
int main(){
init();
// while(cin >> n){
// cout << fir[n] << endl;
// }
LL l,r,k;
cin >> l >> r >> k;
cout << solve(l,r,k) << endl;
return ;
}