Official

E - Divide Both Editorial by physics0523

この問題は、ヒントを次々に出していく形で解説します。ヒントを見る際は、次のヒントに進む前に現在のヒントから得た情報を考察してみてください。

hint 1まず、すべての正整数 $i$ について、整数組 $(i,i)$ は絶対に条件を満たすことがありません。最大公約数が $i$ となり、$\frac{x}{g} = 1$ および $\frac{y}{g} = 1$ となるからです。このことと問題の構造から、 $x < y$ として数えた上で、その答えを $2$ 倍すればよいことが分かります。実はこれにより、問題文の $3$ つの条件のうち $1$ つが無視できます。その条件とはどれでしょうか。
hint 2$x < y$ である限り、条件 $\frac{y}{g} \neq 1$ は必ず成立する条件となります。なぜなら、必ず $g \le x < y$ が成立するからです。ここで、 $g \neq 1$ と $\frac{x}{g} \neq 1$ というふたつの条件をなるべく別々に取り扱えないかを考えます。
hint 3$g \neq 1$ となる場合、すなわち $2$ 整数が互いに素でない整数の組をまず数えます(-> hint 4-1)。その後、 $\frac{x}{g}=1$ となってしまう場合を引き去ることを考えます(-> hint 4-2)。
hint 4-1互いに素でない整数の組 $x,y$ ($L \le x,y \le R$)を数えます。これには、包除原理を用います。具体的には、以下のようにすると求められます。
  • 全ての 同じ素因数を $2$ つ以上含まない整数 $k$ ($2 \le k \le R$) について、 $k$ の倍数がいくつあるかを求め、これを $A$ とします。これは $\lfloor \frac{R}{k} \rfloor - \lfloor \frac{L-1}{k} \rfloor$ とできます。
  • その後、$k$ に含まれる素因数の数が奇数であれば、 $_AC_2$ を答えに足す。偶数であれば、 $_AC_2$ を答えから引く。 $k$ に何種類の素因数が含まれるかは、エラトステネスの篩の要領で予計算することができます。
hint 4-2$g \neq 1$ であるのに、 $\frac{x}{g}=1$ となってしまう場合は、いくつあるでしょうか。
式を少し変形すると、 $x=g$ となります。$g$ は $x,y$ の最大公約数なので、 $x=g$ となるための必要十分条件は $y$ が $g$ の倍数であることです。
これを満たす整数組 $(x,y)$ ($L \le x < y \le R$) の総数は、 $\displaystyle \sum_{g=\max(2,L)}^R \lfloor \frac{R}{g} - 1\rfloor$ という式で表されます。

解法ここまで来ればこの問題は解けたも同然です。hint 3で述べた通りの方針で実装すればよいです。最後に答えを \(2\) 倍する点に注意してください。計算量はエラトステネスの篩の要領で素因数の種類数を数える部分がボトルネックとなり、 \(O(R \log \log R)\) となります。
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: