[abc] AtCoder Beginner Contest 206 E

前言

t a g : tag : tag: 难题(对我来说 数学 容斥 gcd 传送门 :

题意

给定 L , R L,R L,R询问有多少对 ( x , y ) (x,y) (x,y)满足条件

条件

• g = g c d ( x , y ) g = gcd(x,y) g=gcd(x,y)
• x / g ! = 1 , y / g ! = 1 , g ! = 1 x/g !=1,y/g!=1,g!=1 x/g!=1,y/g!=1,g!=1

L , R ∈ ( 1 , 1 0 6 ) L,R \in(1,10^6) L,R∈(1,106)

思路

首先不考虑 x ≠ g , y ≠ g x\neq g,y\neq g x​=g,y​=g,只考虑 g ≠ 1 g\neq1 g​=1,相当于先从大集合考虑

我们设 f ( k ) f(k) f(k)为 g c d ( x , y ) = k gcd(x,y)=k gcd(x,y)=k的数量 f ′ ( k ) f'(k) f′(k)为 g c d ( x , y ) gcd(x,y) gcd(x,y)是 k k k倍的数量

我们知道区间 [ 1 , N ] [1,N] [1,N]中能被 x x x整除的数量为 N x \frac{N}{x} xN​,即 x x x的倍数的数量

因此 f ′ ( k ) = ( R k − L − 1 k ) ∗ ( R k − L − 1 k ) ) = ( R k − L − 1 k ) 2 f'(k)=(\frac{R}{k}-\frac{L-1}{k})*(\frac{R}{k}-\frac{L-1}{k}))=(\frac{R}{k}-\frac{L-1}{k})^2 f′(k)=(kR​−kL−1​)∗(kR​−kL−1​))=(kR​−kL−1​)2

f ( k ) = f ′ ( k ) − f ( 2 k ) − f ( 3 k ) f(k)=f'(k)-f(2k)-f(3k) f(k)=f′(k)−f(2k)−f(3k)

然后我们需要考虑 x ≠ g 且 y ≠ g x\neq g且y\neq g x​=g且y​=g

为了方便计算,我们将其拆分成对立事件即 x = g x=g x=g和 y = g y=g y=g

因为 g c d ( x , y ) = g gcd(x,y)=g gcd(x,y)=g,对于每一个 x = g x=g x=g我们都有 x ∣ y x|y x∣y,因此我们可以取 y = x , 2 x , 3 x y=x,2x,3x y=x,2x,3x共有 R x \frac{R}{x} xR​

同理对于 y = g y=g y=g我们可以有 R y \frac{R}{y} yR​个

因为 ( x , y ) (x,y) (x,y)具有对称性,因此上面的二者数量相等,同时又因为 ( x , x ) 和 ( y , y ) (x,x)和(y,y) (x,x)和(y,y)有重复

因此答案计算为 : ∑ k = 2 R f ( k ) − ∑ x = L R ( R x ∗ 2 − 1 ) \sum_{k=2}^Rf(k)-\sum_{x=L}^R(\frac{R}{x}*2-1) ∑k=2R​f(k)−∑x=LR​(xR​∗2−1)

Code:

// Problem: E - Divide Both
// Contest: AtCoder - AtCoder Beginner Contest 206（Sponsored by Panasonic）
// URL: https://atcoder.jp/contests/abc206/tasks/abc206_e
// Memory Limit: 1024 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include 
#include 
#include 
#include 
#include 
#include 
#include 
using namespace std;
#define IOS  ios::sync_with_stdio(false);
#define CIT  cin.tie(0);
#define COT  cout.tie(0);

#define ll long long
#define x first
#define y second
#define pb push_back
#define endl '\n'
#define all(x) (x).begin(),x.end()
#define Fup(i,a,b) for(int i=a;i=b;i--)

typedef priority_queue  Pri_m;
typedef pair pii;
typedef vector VI;
map mp;
const int N = 1e6+10;
ll f[N];
int l,r;
void solve(){
	cin>>l>>r;
	l--;
	ll res = 0 ;
	
	for(int i = r;i>=2;i -- ){
		int w = r/i - l/i;
		f[i] = 1ll*w*w;
		
		for(int j = i*2;j