November Lunchtime 2020 (Div. 1) Fractions

問題のリンク

問題概要

自然数 $N$ が与えられる。次の条件を満たす自然数 $(i,j)$ の組の総数を求めよ。

• $1 \leq i,j \leq N$
• $\frac{i}{i+1} \cdot \frac{j+1}{j}$ と $ \frac{m}{m+1} $ が等しくなる自然数 $ m $ が存在する

制約

• $1 \leq N \leq 10^{6}$

解法

条件を満たすペアについて常に $i \lt j$ が成立する。

$\frac{i}{i+1} \cdot \frac{j+1}{j} = \frac{m}{m+1}$ を $ m $ について解くと、

$$m = \frac{i(j+1)}{j-i}$$

が得られる。$k=j-i$ とおいて $ i $ を消去すると、

$$ \begin{eqnarray} m &=& \frac{(j-k)(j+1)}{k} \\ &=& \frac{j(j+1)}{k} - (j+1) \end{eqnarray} $$

ここで求めるべきは $1 \leq j \leq N$ のそれぞれに対して $ j $ 未満の $j(j+1)$ の約数の総数を足し合わせたもの、と問題を言い換えることができる。

ところで $ n $ の正の約数の個数を $d(n)$ と表すことにすると、$ j $ と $ j+1 $ は互いに素であるから、$d(j(j+1)) = d(j) \cdot d(j+1)$ が成立する。

$j(j+1)$ は平方数でないので、$ j $ 以下の約数の個数は $\frac{d(j(j+1))}{2}$ 個。ここから $j$ の分として 1 引いたものを足し合わせれば良い。

実装

#include <bits/stdc++.h>
using namespace std;
typedef long long int ll;

int main(){
    int n; cin >> n;
    vector<ll> d(n+2);
    for(int i=1;i<=n+1;i++){
        for(int j=i;j<=n+1;j+=i) d[j]++;
    }
    ll res=0;
    for(int j=1;j<=n;j++){
        res+=d[j]*d[j+1]/2-1;
    }
    printf("%lld\n",res);
}