题意：

给出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 
     
      #define LL long longusing namespace std;const int MAXN = 30000000 + 1;bool check[MAXN];int prime[2000000],fir[MAXN],tot;LL ans,n;int ma;void init(){    tot = 0;    memset(check,false,sizeof(check));    for(int i=2;i
      
       = MAXN) break;            check[i * prime[j]] = true;            fir[i * prime[j]] = prime[j];            if(i % prime[j] == 0) break;        }    }//    printf("tot = %d\n",tot);}bool is_prime(LL k){    if(k < MAXN)        return fir[k] == k;    for(int i=0;i
       
         k) break;        if(k % prime[i] == 0) 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+1,now,f);    dfs(p+1,now * prime[p],-f);}LL cal(LL r,LL k){    ans = 0;    n = r / k;    if(n < MAXN){        for(int i=1;i<=n;++i){            if(i == 1 || fir[i] >= k)                 ++ans;        }        return ans;    }    else{        ma = 0;        for(;ma
        
         > n){//        cout << fir[n] << endl;//    }    LL l,r,k;    cin >> l >> r >> k;    cout << solve(l,r,k) << endl;    return 0;}