Official
After a little transformation we obtain $x=g$. Since $g$ is the GCD of $x$ and $y$, $x=g$ if and only if $y$ is a multiple of $g$.
The number of such pairs of integers $(x,y)$ ($L \le x < y \le R$) can be expressed as $\displaystyle \sum_{g=\max(2,L)}^R \lfloor \frac{R}{g} - 1\rfloor$.
E - Divide Both Editorial by en_translator
We will provide you some step-by-step hints as an editorial. Before advancing the next hint, consider the information you have obtained so far.
hint 1
First, for every integer $i$, the pair of integers $(i, i)$ can never satisfy the conditions, since the greatest common divisor (GCD) is $i$, $\frac{x}{g} = 1$, and $\frac{y}{g} = 1$. From this fact and the structure of the problem, we can count the number of those such that $x < y$ and multiply it by two afterwards. Actually, one of the three conditions in the problem statement can be eliminated by this fact. Which is it?hint 2
As long as $x < y$, the condition $\frac{y}{g} \neq 1$ is always true, because $g \le x < y$. Here, we try to treat the two conditions $g \neq 1$ and $\frac{x}{g} \neq 1$ as separately as possible.hint 3
We first consider the case where $g \neq 1$, i.e. count the number of integer pairs such that two integers are relatively prime (-> hint 4-1). Then, we consider subtracting the case where $\frac{x}{g}=1$ (-> hint 4-2).hint 4-1
We count the number of pairs of coprime integers $x,y$ ($L \le x,y \le R$). We use inclusion-exclusion principle. Specifically, it can be counted as follows.- For every integer $k$ ($2 \le k \le R$) that does not have two or more same prime factors, count the number of multiples of $k$, obtained by $\lfloor \frac{R}{k} \rfloor - \lfloor \frac{L-1}{k} \rfloor$, which we will denote $A$.
- Then, if $k$ has odd number of prime factors, we add $_AC_2$ to the answer; otherwise we subtract $_AC_2$ from the answer. The number of distinct prime factors in $k$ can be precalculated in the same way to the Eratosthenes' sieve.
hint 4-2
How many pairs satisfies $\frac{x}{g}=1$ although $g \neq 1$?After a little transformation we obtain $x=g$. Since $g$ is the GCD of $x$ and $y$, $x=g$ if and only if $y$ is a multiple of $g$.
The number of such pairs of integers $(x,y)$ ($L \le x < y \le R$) can be expressed as $\displaystyle \sum_{g=\max(2,L)}^R \lfloor \frac{R}{g} - 1\rfloor$.
Solution
Now the problem is virtually solved. We can implement it just as described in hint 3. Do not forget to multiply the answer by two at last. The time complexity is \(O(R \log \log R)\), where the bottle neck is counting the number of distinct prime factors.Sample code in C++
#include<bits/stdc++.h>
using namespace std;
int main(){
long long l,r;
cin >> l >> r;
long long res=0;
vector<int> cnt(1048576,0);
for(long long i=2;i<=r;i++){
if(cnt[i]!=0){continue;}
for(long long j=i;j<=r;j+=i){cnt[j]++;}
for(long long j=i*i;j<=r;j+=i*i){cnt[j]=-1000000007;}
}
for(long long i=2;i<=r;i++){
if(cnt[i]<0){continue;}
long long cc=(r/i)-((l-1)/i);
if(cnt[i]%2){res+=(cc*(cc-1))/2;}
else{res-=(cc*(cc-1))/2;}
}
for(long long i=max(2ll,l);i<=r;i++){res-=(r/i-1);}
cout << 2*res << '\n';
return 0;
}
posted:
last update: