牛客練習賽44_C:小y的質數 ( 容斥原理 )

題目大意:

由于這是一個區間篩質數的模闆題。是以小k不屑于去寫。

是以出題人隻好yy了另一道題。

定義k生互質數為滿足y + k與y - k互質的數。

現在給出區間[L,R],你需要輸出區間内k生互質數有多少對 我們說一對k生互質數在區間[L,R]内,當且僅當

y+k ∈ [L,R] 且 y−k ∈ [L,R]。

題目要求求 [l,r] 内 gcd(y,y + 2 * k) = 1 的所有y，因為gcd(y, y + 2 * k) = gcd(y, 2 * k)，隻需要在[l,r - 2 * k]範圍内找滿足要求的數就行了。

但是依然很大，暴力是必然會T的，可以用容斥原理，令 r = r - 2 * k（友善表示）。區間[l,r] 的數字總共有 r - l + 1個，要扣掉gcd > 1的情況。

可以分解gcd > 1的情況：對 2 * k 進行素數分解，[l,r] 所有gcd > 1的數字集合中 可能包括 i 種和 2 * k 相同的素因子，枚舉一下用容斥原理扣掉，先扣掉包括一種 相同素因子的數的個數， 然後加上 包括 兩種相同素因子的數的個數。。。。一路搞到包括所有素因子（容斥原理）。至于有多少個數包含這些數因子，除一下就知道了。

枚舉包括幾種素因子，可以用枚舉子集的方法，先求出 2 * k 所有不同的素數因子集合（不會超過15種），然後可以用二進制枚舉子集，或用DFS搜尋，複雜度最大 O(15 * 2 ^ 15)；

這裡的寫法是一路從包含0種枚舉過去。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
ll l,r,k;
int cnt = 0;
long long p[30];
int main(){
 	scanf("%lld%lld%lld",&l,&r,&k);
 	k *= 2;
 	r -= k;
 	l -= 1;
 	ll ans = 0;
 	if(l > r){
  		printf("0\n");
  		return 0;
 	}
 	for(ll i = 2; i * i <= k; i++){
  		if(k % i == 0){
   			p[++cnt] = i;
   			while(k % i == 0)
   	 			k /= i;
  		}
 	}	 
 	if(k > 1) p[++cnt] = k;
 	for(int i = 0; i < (1 << cnt); i++){
  		long long an = 1;
  		for(int j = 0; j < cnt; j++){
   			if((1 << j) & i){
    				an *= p[j + 1];
    				an *= -1;
   			}
  		}
  		if(l >= 0)
   			ans += r/an - l/an;
  		else ans += r/an;
 	}
 	printf("%lld\n",ans);
 	return 0;
}