[3.10] よく使う数学処理

[akito119]

この節で学ぶこと

• Math
• 最大公約数
• 素数判定
• 累積和

解説

最大公約数、素数判定、累積和は多くの問題で再利用できる基本処理です。特に累積和は区間の合計を高速に求めるために使います。

コード例

long[] prefix = new long[n + 1];
for (int i = 0; i < n; i++) {
    prefix[i + 1] = prefix[i] + values[i];
}
long rangeSum = prefix[r] - prefix[l];

コードをそのまま写すだけでなく、値や条件を変更して実行結果がどう変わるか確認してください。

確認問題

1. 「Math」は何のために使いますか。
2. 「累積和」を使うときに注意すべき点を説明してください。
3. この節のコードや手順を、自分の言葉で説明してください。

演習

この節で学んだ「よく使う数学処理」を使う小さなプログラムを作ってください。値を最低2通り試し、予想した結果と実際の結果が一致することを確認しましょう。

まとめ

Math、最大公約数、素数判定、累積和を学びました。分からない点が残った場合は、コードや手順を小さく分けて一つずつ確かめてください。

次のセクション

次は「第3章 総合演習」へ進みます。

APG4bの対応問題

• EX26「3.06」