Leap Year Count

解説

$1$から$N$までの自然数のうち、$(aの倍数) \cap (lcm(a,b)の倍数でない)$ となるような自然数の数を求めれば良いです。

• $1$から$N$までの自然数のうちの$k$の倍数の個数は $N/k$を整数値に切り捨てた値として$O(1)$で求めることができます。
• $lcm(a,b)$ は $gcd(a,b)$の値をユークリッドの互除法を利用して求めることで$O(log(max(a,b)))$で求めることができます。

以上のことから、答えを求めることができます。時間計算量はユークリッドの互除法がボトルネックとなり、$O(log(max(a,b)))$ です。コンピューターは一秒に $10^6$ 回の計算ができるため、 本制約においては余裕を持って実行時間制限に間に合います。 よって、この問題を解くことができました。

追記

この問題の制約において、C++のlonglong型の最大値(約$9 \times 10^{18}$) を $lcm(a,b)$ が超えてしまうことが考えられます。よって、C++のような固定長の整数を扱う場合は次のように考えます。

• $\displaystyle lcm(a,b) = \frac{ab}{gcd(a,b)}$ より、$N < lcm(a,b)$

つまり、$\displaystyle N < \frac{ab}{gcd(a,b)} \Longleftrightarrow \frac{N}{b} < \frac{a}{gcd(a,b)}$ のとき $lcm(a,b)$で割り切れる$1$から$N$までの自然数は0個 と判定、そうでなければ実際に$lcm(a,b)$で割り切れる$1$から$N$までの自然数の数を求める、という感じで実装することでオーバーフローを回避しながら計算を進めることができます。