約数やくすうdivisorと素因数分解そいんすうぶんかいprime factorizationを処理しょりする定石じょうせき

11. 使つかう場面ばめん

• 約数やくすうの個数こすう・総和そうわ、$\text{[PARSE ERROR: Undefined("Command("gcd")")]}$\gcd、$\mathrm{lcm}$\operatorname{lcm} を求もとめる
• 「何乗なんじょうで割わり切きれるか」「平方数へいほうすうか」を判定はんていする
• 積せきや整除条件せいじょじょうけんがあり、整数せいすうそのものより各素因数かくそいんすうの指数しすうを追おう方ほうが簡潔かんけつな問題もんだい

22. 見分みわけ方かた

積せき・約数やくすう・倍数ばいすうは、まず $n=\prod p_{i^{a_i}}$n=\prod p_i^{a_i} と書かいて素因数そいんすうprime factorごとの指数しすうexponentへ翻訳ほんやくする。和わ $a+b$a+b や余あまりが主役しゅやくなら、素因数分解そいんすうぶんかいを急いそがず合同式ごうどうしきまたは互除法ごじょほうを選えらぶ。

33. 使つかう公式こうしき

$\tau \left(n\right)$\tau(n) を $n$n の正せいの約数やくすうの個数こすう、$\sigma \left(n\right)$\sigma(n) をその総和そうわとする。$n=\prod _{i=1}^r{p}_{i^{a_i}}$n=\prod_{i=1}^r p_i^{a_i}（$p_i$p_i は相異あいことなる素数そすう、$a_i\text{[PARSE ERROR: Undefined("Command("ge")")]}1$a_i\ge1）なら

適用条件てきようじょうけんは $n$n が正整数せいせいすうで、素因数分解そいんすうぶんかいが完全かんぜんであることである。各約数かくやくすうは $\prod p_{i^{b_i}}$\prod p_i^{b_i} と一意いちいに書かけ、指数しすうを独立どくりつに選えらべるため積せきになる。

44. 解とき方かたの手順てじゅん

1. 対象たいしょうを正せいの素数そすうの積せきへ完全かんぜんに分解ぶんかいする。
2. 問といを「各素数かくそすうの指数しすうをどう選えらぶか」へ翻訳ほんやくする。
3. 個数こすうなら選択肢数せんたくしすうを掛かけ、$\text{[PARSE ERROR: Undefined("Command("gcd")")]}$\gcd なら最小さいしょう、$\mathrm{lcm}$\operatorname{lcm} なら最大さいだいを取とる。
4. 元もとの条件じょうけんへ戻もどし、積せきの復元ふくげんと整除せいじょを確認かくにんする。

55. 判別はんべつと注意点ちゅういてん

$\text{[PARSE ERROR: Undefined("Command("gcd")")]}$\gcd の値あたいだけなら、大おおきな整数せいすうを完全かんぜんに素因数分解そいんすうぶんかいするより互除法ごじょほうが速はやい。素因数そいんすうの構成こうせいや約数やくすうの全体ぜんたいが必要ひつようなときに本定石ほんじょうせきを選えらぶ。負ふの整数せいすうでは約数やくすうを正せいの約数やくすうに限定げんていするか、符号ふごうも数かぞえるかを問題文もんだいぶんで確認かくにんする。$1$1 は空積くうせきであり、$\tau \left(1\right)=1$\tau(1)=1 である。

66. 落おとし穴あな

• 分解途中ぶんかいとちゅうの合成数ごうせいすうを素数そすうとみなして公式こうしきを適用てきようする
• $\text{[PARSE ERROR: Undefined("Command("gcd")")]}$\gcd で指数しすうの最大値さいだいち、$\mathrm{lcm}$\operatorname{lcm} で最小値さいしょうちを取とる
• 約数やくすうの指数しすうを $1$1 から選えらび、指数しすう $0$0 の選択肢せんたくしを落おとす

77. 関連かんれんリンク

88. 演習えんしゅうリンク