链接：https://ac.nowcoder.com/acm/contest/634/C
来源：牛客网
题目描述
给出一个区间[L,R]，求出[L,R]中孪生质数有多少对。
由于这是一个区间筛质数的模板题。所以小k不屑于去写。
所以出题人只好yy了另一道题。
定义k生互质数为满足y + k与y - k互质的数。
现在给出区间[L,R],你需要输出区间内k生互质数有多少对
我们说一对k生互质数在区间[L,R]内,当且仅当y+k∈[L,R]y+k∈[L,R]且y−k∈[L,R]y−k∈[L,R]
输入描述:
一行三个数字L,R,k
输出描述:
一行一个数字表示区间[L,R]内的k生互质数的对数
备注:
0≤L,R≤10180≤L,R≤1018
1≤k≤1013
由gcd(x,x+2*k)=gcd(x,2*k)可把问题转化为在区间(l,r-2*k)内有多少个数gcd(x,2*k)等于1；
若两个数求gcd的结果为1,则说明这两个数的最大公因数为1，所以可以将2*k分解质因数并且去重，再使用容斥原理算出区间内有多少个数的因子包含
求出的2*k的质因子；
容斥原理：计算n集合并集的大小，先加上单个集合的大小，再减去所以两个集合相交部分，再加上所以三个集合的相交部分，再减去。。以此类推到n个集合
这题先用分解质因子求出2*k的质因子,再用dfs跑出所有因子的组和
代码如下
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll l,r,k;
ll primson[65];
ll ans;
ll low,up;
int id;
void getprim(ll k)
{
for(int i = 2;i*i <= k;++i)
{
if(k%i==0)
{
primson[++id]=i;
while(k%i==0)
k/=i;
}
}
if(k > 1)
primson[++id]=k;
}
void dfs(int index,int num,ll mul)
{
if(index>id)
{
if(num&1)
ans-=up/mul-low/mul;
else
ans+=up/mul-low/mul;
return ;
}
dfs(index+1,num,mul);
dfs(index+1,num+1,mul*primson[index]);
}
void solve()
{
low=l-1;
up=r-2*k;
if(low<0)
low=0;
if(up<low)
return;
getprim(2*k);
dfs(1,0,1ll*1);
}
int main()
{
scanf("%lld%lld%lld",&l,&r,&k);
solve();
printf("%lld\n",ans);
return 0;
}