前言
$tag :$ 难题(对我来说
数学
容斥
gcd
传送门 :
题意
给定$L,R$询问有多少对$(x,y)$满足条件
条件
- $g = gcd(x,y)$
- $x/g !=1,y/g!=1,g!=1$
$L,R \in(1,10^6)$
思路
首先不考虑$x\neq g,y\neq g$,只考虑$g\neq1$,相当于先从大集合考虑
我们设
$f(k)$为$gcd(x,y)=k$的数量
$f’(k)$为$gcd(x,y)$是$k$倍的数量
我们知道区间$[1,N]$中能被$x$整除的数量为$\frac{N}{x}$,即$x$的倍数的数量
因此
$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)=f’(k)-f(2k)-f(3k)$
然后我们需要考虑 $x\neq g且y\neq g$
为了方便计算,我们将其拆分成对立事件即$x=g$和$y=g$
因为$gcd(x,y)=g$,对于每一个$x=g$我们都有$x|y$,因此我们可以取$y=x,2x,3x$共有$\frac{R}{x}$
同理对于$y=g$我们可以有$\frac{R}{y}$个
因为$(x,y)$具有对称性,因此上面的二者数量相等,同时又因为$(x,x)和(y,y)$有重复
因此答案计算为 :
$\sum_{k=2}^Rf(k)-\sum_{x=L}^R(\frac{R}{x}*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 <iostream>
#include <vector>
#include <map>
#include <cstring>
#include <queue>
#include <set>
#include <algorithm>
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++)
#define Fde(i,a,b) for(int i=a;i>=b;i--)
typedef priority_queue<int,vector<int>,greater<int>> Pri_m;
typedef pair<int,int> pii;
typedef vector<int> VI;
map<int,int> 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<=r;j+=i)f[i]-=f[j];
res += 1ll*f[i];
}
for(int i=l+1;i<=r;i++){
if(i == 1)continue;
res-=1ll*r/i*2-1;
}
cout<<res<<endl;
}
int main(){
//int t;cin>>t;while(t--)
solve();
return 0 ;
}