Problem - D - Codeforces
問題概要
整数 $N$ が与えられる。
$N$ 頂点 $0$ 辺のグラフ $G$ を用意する。頂点番号は $1,2,\dots,N$ である。
$\gcd(i,j) \neq 1$ を満たす全ての整数組 $1 \le i < j \le N$ に対し、 $G$ の頂点 $i,j$ 間に長さ $1$ の無向辺を張る。
$1 \le i,j \le N$ なる整数組に対し、以下の関数 $f$ を定義する。
- $f(i,j) =$ ( $G$ 上での頂点 $i,j$ 間の最短距離) ( 頂点 $i,j$ が $G$ 上で連結 )
- $0$ $( \rm{otherwise} )$
$\displaystyle \sum^{N}_{i=1} \sum^{N}_{j=i+1} f(i,j)$ を求めよ。
制約
・ $1 \le N \le 10^7$
まず簡単に実験をしてみる。
$N=14$ の場合 (ハイフンは到達不能)
色々実験してみると、
- $2p > N$ なる素数 $p$ からは他の誰にも到達できなさそうなこと
- $f(i,j) \le 3$ が成り立ちそうなこと
がわかるので、証明しにかかる。
まず $x$ が 素数であり $2x > N$ である場合、 $x$ は孤立頂点となり全ての $i$ に対し $f(x,i) = 0$ である。
また $1$ も孤立頂点であるので全ての $i$ に対し $f(1,i)=0$ である。
相異なる $i,j$ に対して $f(i,j) = 1$ であることの必要十分条件は $\gcd(i,j) \neq 1$ 。辺の貼り方より明らか。
ここまでで処理されていない $f(i,j)$ を吟味していく。ここで、 $\gcd(i,j) = 1$ であるケースを考えていくことに注意されたい。
$f(i,j)=2$ ということは $i,j$ の間に $1$ 人仲立ちを立てれば到達可能になるということ。ではどのような仲立ちを立てるべきか?
答えは ( $i$ の最小素因数 ) $\times$ ( $j$ の最小素因数 ) 。これが考えうる最も小さい仲立ちである。この値が $N$ 以下ならこの仲立ちが存在していることになる。
では、到達可能なら $f(i,j) \le 3$ が示せるだろうか？答えは Yes 。証明は以下。
「到達可能」という前提から $i,j$ の最小素因数の $2$ 倍は $N$ 以下であることに注意されたい。ここで、
$i$ から ( $i$ の最小素因数 $\times$ $2$ ) に
( $i$ の最小素因数 $\times$ $2$ ) から ( $j$ の最小素因数 $\times$ $2$ ) に
( $j$ の最小素因数 $\times$ $2$ ) から $j$ に
直接移動できることが分かる。これより題意は示された。
さて、問題は以下に帰着される。
・$f(i,j) = 0$ if $i$ が孤立頂点 or $i=j$
・$f(i,j) = 1$ if $\gcd(i,j) \neq 1$
・$f(i,j) = 2$ if ( $i$ の最小素因数 ) $\times$ ( $j$ の最小素因数 ) $\le N$
・$f(i,j) = 3$ otherwise
が分かったので、元の問題を解け。
但し複数に該当する場合より上の条件を優先する。
$\gcd(i,j) = 1$ かつ ( $i$ の最小素因数 ) $\times$ ( $j$ の最小素因数 ) $\le N$ なる $i,j$ の数を数えに行くのが素直だが、かなり厳しそうなので方針転換。
「最初は全ての孤立頂点でない相異なる頂点の組 $i,j$ に対して $f(i,j)=3$ だと思って、うまいこと値を引いていけないか？」を考える。
・ $\gcd(i,j) \neq 1$ なら 1 減算 ... (i)
・( $i$ の最小素因数 ) $\times$ ( $j$ の最小素因数 ) $\le N$ なら 1 減算 ... (ii)
ができれば上手くいきそう。
しかし、 (i) かつ (ii) でない、即ち $\gcd(i,j) \neq 1$ だが ( $i$ の最小素因数 ) $\times$ ( $j$ の最小素因数 ) $> N$ であるような組 $i,j$ があればそこの値が $2$ として取り扱われてしまい、困ってしまう。
しかし、驚くべきことにそのような $i,j$ の組は存在しないことが証明できる。証明は以下。
$\gcd(i,j) \neq 1$ である相異なる $i,j$ の組を考え、それが (ii) を必ず満たすことを示す。
$\gcd(i,j) \neq 1$ なので $i,j$ に何らかの素因数が共通していることがわかる。
$i,j$ に $\sqrt{N}$ 以下の素因数が共通している場合、 ( $i$ の最小素因数 ) $\times$ ( $j$ の最小素因数 ) $\le N$ なのは共通している素因数より明らか。
逆に $i,j$ に $\sqrt{N}$ 超過の素因数しか共通していない場合、それを $p$ とおく (ここで、 $p$ は単一の素数であることに注意 )。
$i < j$ として一般性を失わない。
$i = p$ である場合、 $j$ が $\frac{N}{p}$ 以下の何らかの素因数を含んでいることになり、それと $p$ の積が $N$ となり題意を満たす。
また、 $i = p \times q$ ( $q$ は $2$ 以上の整数 ) である場合は ( $i$ の最小素因数 ) $\le q$ かつ ( $j$ の最小素因数) $\le p$ であるから $q \times p \le N$ より題意を満たす。
以上より示された。
あとはこれを実際に計算していく。
$\gcd(i,j) \neq 1$ かつ $i < j$ なる $i,j$ の組の数は オイラーのφ関数 を使えばエラトステネスの篩をやりながら求まり、 ( $i$ の最小素因数 ) $\times$ ( $j$ の最小素因数 ) $\le N$ なる組の数は最小素因数ごとにバケットソートすれば $O(N \log N)$ で求まる。
Submission #207821818 - Codeforces
$f(i,j)$ の求め方が分かってから、一見不味そうな数え上げを「 (i) かつ (ii) でないものは存在しない」という強力な補題を使って正当性を示しトドメを刺すのが美しい。
