鏈接：https://ac.nowcoder.com/acm/contest/634/C
來源：牛客網(wǎng)

題目描述
給出一個(gè)區(qū)間[L,R]，求出[L,R]中孿生質(zhì)數(shù)有多少對。
由于這是一個(gè)區(qū)間篩質(zhì)數(shù)的模板題。所以小k不屑于去寫。
所以出題人只好yy了另一道題。
定義k生互質(zhì)數(shù)為滿足y + k與y - k互質(zhì)的數(shù)。
現(xiàn)在給出區(qū)間[L,R],你需要輸出區(qū)間內(nèi)k生互質(zhì)數(shù)有多少對
我們說一對k生互質(zhì)數(shù)在區(qū)間[L,R]內(nèi),當(dāng)且僅當(dāng)y+k \in[L,R]y+k∈[L,R]且y-k \in[L,R]y?k∈[L,R]
輸入描述:
一行三個(gè)數(shù)字L,R,k
輸出描述:
一行一個(gè)數(shù)字表示區(qū)間[L,R]內(nèi)的k生互質(zhì)數(shù)的對數(shù)
示例1
輸入
復(fù)制
5 10 1
輸出
復(fù)制
2
說明
分別為(5,7),(7,9)
示例2
輸入
復(fù)制
287 11633 10
輸出
復(fù)制
4532
備注:
0 \leq L,R \leq 10^{18}0≤L,R≤10
18

1 \leq k \leq 10^{13}1≤k≤10
13

思路：
題意為讓你尋找 L 到 R 中 多少 x 使 gcd(x-k,x+k)=1

根據(jù)gcd的性質(zhì)，我們可以得到 gcd(x,x+2 * k ) =1

即 gcd(x,2k)=1

有因?yàn)?題目要求 x+k 小于R

所以 題目可以轉(zhuǎn)化為 l~r-2k 中，有多少個(gè)數(shù) x 使得 gcd(x, 2k)==1

這就是一個(gè)景點(diǎn)的問題了。

即：

對 2 * k 進(jìn)行素?cái)?shù)分解，[l,r] 所有g(shù)cd > 1的數(shù)字集合中 可能包括 i 種和 2 * k 相同的素因子，枚舉一下用容斥原理扣掉，先扣掉包括一種 相同素因子的數(shù)的個(gè)數(shù)， 然后加上 包括 兩種相同素因子的數(shù)的個(gè)數(shù)。。。。一路搞到包括所有素因子（容斥原理）。至于有多少個(gè)數(shù)包含這些數(shù)因子，除一下就知道了。

兩個(gè)細(xì)節(jié)：

r-2k后可以小于l

l可以為0 要判斷 l-1 和0的大小關(guān)系。

細(xì)節(jié)見代碼：

#include <iostream> #include <cstdio> #include <cstring> #include <algorithm> #include <cmath> #include <queue> #include <stack> #include <map> #include <set> #include <vector> #include <iomanip> #define ALL(x) (x).begin(), (x).end() #define sz(a) int(a.size()) #define all(a) a.begin(), a.end() #define rep(i,x,n) for(int i=x;i<n;i++) #define repd(i,x,n) for(int i=x;i<=n;i++) #define pii pair<int,int> #define pll pair<long long ,long long> #define gbtb ios::sync_with_stdio(false),cin.tie(0),cout.tie(0) #define MS0(X) memset((X), 0, sizeof((X))) #define MSC0(X) memset((X), '\0', sizeof((X))) #define pb push_back #define mp make_pair #define fi first #define se second #define eps 1e-6 #define gg(x) getInt(&x) #define chu(x) cout<<"["<<#x<<" "<<(x)<<"]"<<endl using namespace std; typedef long long ll; ll gcd(ll a, ll b) {return b ? gcd(b, a % b) : a;} ll lcm(ll a, ll b) {return a / gcd(a, b) * b;} ll powmod(ll a, ll b, ll MOD) {ll ans = 1; while (b) {if (b % 2)ans = ans * a % MOD; a = a * a % MOD; b /= 2;} return ans;} inline void getInt(int* p); const int maxn = 1000010; const int inf = 0x3f3f3f3f; /*** TEMPLATE CODE * * STARTS HERE ***/std::vector<ll> v; void breakdown(ll x) {for(ll i=2ll;i*i<=x;++i){int cnt=0;while(x%i==0){cnt++;x/=i;}if(cnt){v.push_back(i);}}if(x>1){v.pb(x);} } ll l,r,k; int main() {//freopen("D:\\code\\text\\input.txt","r",stdin);//freopen("D:\\code\\text\\output.txt","w",stdout);gbtb;cin>>l>>r>>k;k<<=1;r-=k;if(l>r){cout<<0<<endl;return 0;}breakdown(k);int len=sz(v);int maxstate=(1<<len)-1;ll ans=0ll;l=max(l-1ll,0ll);for(int i=0;i<=maxstate;++i){int num=0;ll p=1ll;for(int j=0;j<len;++j){if(i&(1<<j)){num++;p*=v[j];}} // cout<<(r/p-l/p)<<" "<<num<<endl;ans+=(r/p-l/p)*((num&1)?-1ll:1ll);}cout<<ans<<endl;return 0; }inline void getInt(int* p) {char ch;do {ch = getchar();} while (ch == ' ' || ch == '\n');if (ch == '-') {*p = -(getchar() - '0');while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 - ch + '0';}}else {*p = ch - '0';while ((ch = getchar()) >= '0' && ch <= '9') {*p = *p * 10 + ch - '0';}} }

轉(zhuǎn)載于:https://www.cnblogs.com/qieqiemin/p/11348842.html

總結(jié)

以上是生活随笔為你收集整理的牛客练习赛44 C小y的质数 （数论，容斥定理）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。