計算量考慮編（数式の変形）ABC179 C - A x B + C

atcoder.jp

うーんこういう問題、絶対解法思いつきませんw

思考の流れ

1. まず全探索ではないことはすぐわかった（Nが10⁶のため、O(N³）になる）
2. なので、A,B,Cの約数列挙かなー？
3. ギブアップ

次に活かしたい点

こういう問題は、下記がポイントかも

• 式をとりあえず変形してみる
• 誰かの値（A、B、C）の値を固定し、全探索する

正解思考の1つ

A, B, Cは正整数とのことなので、A,B,Cに0は含まれない
例えば、のとき、 の値が3 だったら は0になってしまう。
このことから、は必ず1以上になるので、ということになる。
これをさらに変形させれば、となり、になるようなAとBの掛け合わせの組み合わせを考えればよいことに
ここで、ようやくを全探索し、が何個あるかを導けばよい。
公式の解説でもあったが、の場合、 では33通りあるとわかるようなので、下記のコードとなる。

import java.util.Scanner;

public class Main {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();

        int ans = 0;
        for(int i=1; i<=n; i++) {
            ans += (n-1) / i;
        }
        System.out.println(ans);
    }
}