ABC206 E 解答

E - Divide Both（1745）

問題

E - Divide Both

問題文

整数 L, R ( L ≤ R ) が与えられるので、以下の条件を全て満たす整数組
( x, y )の数を求めてください。
・L ≤ x, y ≤ R
・g を x, y の最大公約数とすると、以下が成立する。
　g ≠ 1 かつ x / g ≠ 1 かつ y / g ≠1

制約

入力は全て整数
1 ≤ L ≤ R ≤ 10^6

考察

この問題も愚直に考えれば答えを求めることができます。入力例1を考えてみます。

例) 3 7

ですので、

3 4 5 6 7

となります。一つずつ考えます。まずは3を使いましょう。それぞれの最大公約数を考えます。

gcd(3,4)=1
gcd(3,5)=1
gcd(3,6)=3
gcd(3,7)=1

です。ただ、これらは全て条件を満たしません。3となる場合でも3/3=1なので、適切な組み合わせではありません。残念ですね。次は4です。

gcd(4,3)=1
gcd(4,5)=1
gcd(4,6)=2
gcd(4,7)=1

ここで、gcd(4,6)は条件を満たします。ということで、答えに加えましょう。

これを7までやると晴れて答えが求まります。しかし、毎度のことながら計算時間が間に合いません。

ということで今回は、

各数字の組み合わせを高速に求める

ではなく

少し視点を変えまして、

各最大公約数において何組存在するか

を考えていきます。上の例で言いますと、3をペアに含む場合の組み合わせ、ではなく、最大公約数が3となる組み合わせはいくつあるか、に焦点を当てていきます。この点を誤解してしまうと以下の説明がよくわからなくなりますので、最大公約数で考えてるんだぞ、ということを意識していただければと思います。

では、各最大公約数はいくつの組み合わせを持つのかを考えます。まずは簡単のために条件をいくつか無視します。簡単な条件で求めた後に、追加の条件の分を引いてあげることとします。

一旦、次の条件を無視しましょう。

x/g≠1 かつ  y/g≠1

とにかく、最大公約数 g を持つ組みを求めれば良いです。これを考えるためにもっと条件を緩くしまして、

最大公約数が g の倍数となる組み合わせ

を考えます。g = 2の場合には、g=4,6,8,10...も一緒に数え上げます。

実はこれを求める方法ってそんなに難しくありません。式1つで求まります。

R / g - (L-1) / g

の切り捨てて演算です。具体的に数字を入れてみるとわかると思います。まずはRの方からです。先程の例3 4 5 6 7でg=2としましょう。R/gですので、7/2=3です。7以下の2の倍数は3個ということです。これは、2、4、6なので合ってますね。次はLです。(3-1)/2=1となります。この1は先ほど3より小さい2をカウントしてしまった分ですので、引いてあげまして、結局4、6の2個となります。

ただ今回求めたいのは、g=2の倍数となる組み合わせですので、この値を2乗します。選択肢が2つ合って、xとyでそれぞれ4か6を選ぶためです。このとき同じものを選んでいても大丈夫です。後で引きます。

ということで、g=2の倍数となる組み合わせが求まりました。ただ、2の倍数ですので、g=4もg=6も含まれています。
ここで、最大公約数がgとなる(gの倍数じゃないです)組み合わせの数をf(g)と表現すると、先程の2の倍数の値を用いれば次のような式が成り立ちます。

f(2)=f(2の倍数)-f(4)-f(6)-...

この式の何が嬉しいかと言いますと、gが大きい方から計算をしていくとf(2)を計算する時点で必要な全ての値が求まっている、ということです。

以上により、最大公約数がgとなる組が求まりました。

続きまして、無視した条件を考えます。

x/g≠1 かつ  y/g≠1

この条件のものを引いてあげます。といってもこれはそんなに難しくないです。この条件により除かれるのは、gがその値自身の時です。2であれば片方の数字が2の時ですね。このときの相方の数字の取り方はgの倍数だけありますので、

R/g - (L-1)/g

という先の式と同じ式だけその数字が存在します。もっと言いますと、gが片方の数字と同じになるのはその値がL以上であるため(L-1)/gの項は常に0となるため

R/g

だけで大丈夫です。ただし、x=gの場合とy=gの場合があるのでこの値を2倍しましょう。さらに言いますと、x=y=gを重複してカウントしているため、-1をしましょう。

(R/g)*2 - 1

この値を L(L=1なら2) からRまで計算して、上記の条件を無視した値から引いてあげることで答えが求まります。

以上で考察は終了です。実装しましょう。

実装

#include<bits/stdc++.h>
#define rep(i,n) for(int i=0;i<n;++i)
#define reps(i,s,n) for(int i=s;i<n;++i)
using namespace std;
using ll = long long;
using P = pair<int, int>;
using T = tuple<int, int, int>;


int main()
{
   int l,r;
   cin >> l >> r;
   ll ans = 0;
   vector<ll> f(r + 1,0);
   for (ll g = r; g >= 2; --g)
   {
       ll m = r / g - (l - 1) / g;
       f[g] += m * m;
       for (int t = 2 * g; t <= r; t += g)
       {
           f[g] -= f[t];
       }
       ans += f[g];
   }
   for (int i = max(2,l); i <= r; ++i)
   {
       ans -= r / i*2-1;
   }
   cout << ans << endl;
   return 0;
}

あとがき

問題文を見ますとかなり複雑な約数の問題だと思われますが、切り崩していくと非常にシンプルな計算でACすることが可能です。

このように、いかに簡単な問題に落とし込むか、というのはとっても重要なんですけど、なかなか簡単にはできないですね。私もコンテスト中は、約数の問題だ、難しそう、といった感じでちょっと見ただけです。

「各数字において成立する組み合わせ」から「各最大公約数において成立する組み合わせ」のように、見方といいますか、着目点を変える良い練習になると思いますので、見よう見まねで良いので挑戦してみてはいかがでしょうか。