ABC108

ABC108C

AtCoderサイト

考え方

• a+bをkで割った時のあまりについて考える際に aをkで割ったあまりとbをkで割った時のあまりに分けて考える。
• a,b共にkで割り切れる時a+bはkで割り切れる。a,bをkで割った余りが共にk/2の時も、a+bはkで割り切ることができる。
• 割る数が奇数の時、割った余りがk/2になることはない。そのため割る数が奇数の場合はa,b,cいずれもkで割り切れる必要がある。
• N / K をすることでN以下のKで割り切れる数を出すことができる。
• N / ( K / 2 ) でN以下の( K / 2 ) で割り切れる数を出すことができる。
• a,b,c全てがkで割り切れる場合とa,b,c全てがkで割って( k / 2 )余る時の数を調べれば、a,b,cのどの文字がどの数を選ぶかで3上すれば答えはでる。

実装

        int n = sc.nextInt();
        int k = sc.nextInt();
        long ans;
        if (k % 2 == 0) {
            long a = n / k;           // 因数にkを持つ数の数
            long b = n / (k / 2);   //因数に( k / 2 ) を持つ数の数
            long c = b - a;         // 因数に( k / 2 ) を持つが k を持たない数の数
            ans = c * c * c + a * a * a;
        } else {
            long a = n / k;
            ans = a * a * a;
        }
        System.out.println(ans);

コメント

• コード自体は難しくなかった。
• 考え方が思いうかばず全探査してTLEを起こしてしまった。
• 割り切れるの時には因数に持つことを意識指揮する