题目链接：https://ac.nowcoder.com/acm/contest/634/C
链接：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 思路：
首先看到这个题，数据量这么大，肯定不是暴力，分析表达式：y + k与y - k互质，也就是gcd(y-k,y+k)=1 那么令x=y-k 所以有gcd(x,x+2*k)=1 这就好处理多了 显然x和x不是互质的 那么x和2*k肯定是互质的
所以gcd(x,2*k)互质。 所以这题就转化为求x的取值范围内有多少个数与2*k互质。 有求区间多少个数与某个数互质的算法 看博客：https://www.cnblogs.com/caijiaming/p/10745074.html
但是还是有坑点，具体看代码：
#include<iostream>
#include<vector>
using namespace std;
typedef long long LL;
void solve(LL n,LL l,LL r)
{
vector<LL> p;
for(LL i=;i*i<=n;i++)//求n的所有质因子
{
if(n%i==)
{
p.push_back(i);
while(n%i==)
{
n/=i;
}
}
}
if(n>) p.push_back(n); //容斥
// cout<<"*&"<<endl;
LL ans=;
LL len=p.size(); // cout<<len<<" "<<endl;
for(LL i=;i<((LL)<<len);i++)//二进制枚举
{
// cout<<"*"<<endl;
LL mul=,cnt=;
for(LL j=;j<len;j++)
{
// cout<<"*"<<endl;
if(i&(<<j))
{
cnt++;
mul*=p[j];
}
}
LL sum=(l-)/mul;
LL sum1=r/mul; if(cnt&) ans+=sum1-sum;
else ans-=sum1-sum;
}
if(l==) ans++;//坑点！！
cout<<(r-l+)-ans<<endl;
}
int main()
{
LL l,r,k;
cin>>l>>r>>k;
// if(l>r) swap(l,r);
if((r-*k)>=l) solve(k*,l,r-*k);
else cout<<""<<endl;
return ;
}