牛客练习赛44C
链接：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生互质数的对数示例1
输入
复制5 10 1
输出
复制2
说明
分别为(5,7),(7,9)示例2
输入
复制287 11633 10
输出
复制4532
备注:
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 low,high; ll cnt; int d; set<ll>s; map<ll,int>mp; map<ll,int>mmp; void getprim(ll x) { for(int i = 2;i <= x;++i) { while(x!=i) { if(x%i==0) { s.insert(i); x/=i; } else break; } } if(x!=0) s.insert(x); } void dfs(int num,ll mul) { set<ll>::iterator ite; if(mmp[mul]) return; mmp[mul]=1; if(num&1) { cnt+=high/mul-low/mul; } else if(num!=0) cnt-=high/mul-low/mul; for(ite=s.begin();ite!=s.end();++ite) { if(!mp[*ite]) { mp[*ite]=1; dfs(num+1,mul*(*ite)); mp[*ite]=0; } } } int main() { ll l,r,k; cin>>l>>r>>k; low=l-1; high=r-2*k; if(low<0) low=0; if(low>high){ printf("0\n"); return 0; } getprim(2*k); dfs(0,1); printf("%lld\n",high-low-cnt); return 0; }
更多精彩
