チャレンジ #274: 完全数
オプション
- RSS フィードを購読する
- トピックを新着としてマーク
- トピックを既読としてマーク
- このトピックを現在のユーザーにフロートします
- ブックマーク
- 購読
- ミュート
- 印刷用ページ
AYXAcademy
Alteryx
06-18-2024
07:15 AM
- 新着としてマーク
- ブックマーク
- 購読
- ミュート
- RSS フィードを購読する
- ハイライト
- 印刷
- モデレーターに通知する
こんにちは、Maveryx!
このチャレンジは、最もクリエイティブなチャレンジ貢献者の 1 人であるIppei Nakagawaによって提出されました。 @gawa さん、貴重な貢献に感謝します。また、Inspire2024 中に直接お会いできて嬉しかったです!
完璧な人は神話かもしれませんが、完全な数は現実のものです。完全数とは、(それ自体を除く) 約数の合計に等しい正の整数です。
あなたの課題は、入力データに与えられた1 ~ 10,000 の範囲の整数のリストから、その中に隠されている完全数を特定することです。たとえば、最小の完全数は 6 で、これは6の約数 1、2、3 の合計です。
復習が必要ですか?アカデミーでこのレッスンを復習して準備を整えてください。
健闘を祈ります!
Qiu
21 - Polaris
06-19-2024
12:35 AM
- 新着としてマーク
- ブックマーク
- 購読
- ミュート
- RSS フィードを購読する
- ハイライト
- 印刷
- モデレーターに通知する
できました。
DaisukeTsuchiya
14 - Magnetar
06-19-2024
02:10 AM
- 新着としてマーク
- ブックマーク
- 購読
- ミュート
- RSS フィードを購読する
- ハイライト
- 印刷
- モデレーターに通知する
KosukeUchihashi
アステロイド
06-19-2024
05:18 PM
- 新着としてマーク
- ブックマーク
- 購読
- ミュート
- RSS フィードを購読する
- ハイライト
- 印刷
- モデレーターに通知する
gawa
16 - Nebula
06-19-2024
05:55 PM
- 新着としてマーク
- ブックマーク
- 購読
- ミュート
- RSS フィードを購読する
- ハイライト
- 印刷
- モデレーターに通知する
@KosukeUchihashi 挑戦ありがとうございます。ネタバレに、計算量を減らすロジックを書きます
スポイラ
整数Xの約数は、必ず [X/2] 以下なので、行生成のループ条件を以下にすることで、約数候補の探索総数を約半分に減らせます。
私の環境では4.5秒➡3.0秒まで短縮できました
私の環境では4.5秒➡3.0秒まで短縮できました
SuguruYoshinaga
コメット
06-19-2024
11:07 PM
- 新着としてマーク
- ブックマーク
- 購読
- ミュート
- RSS フィードを購読する
- ハイライト
- 印刷
- モデレーターに通知する
できました。
AkimasaKajitani
17 - Castor
06-20-2024
06:50 AM
- 新着としてマーク
- ブックマーク
- 購読
- ミュート
- RSS フィードを購読する
- ハイライト
- 印刷
- モデレーターに通知する
Yoshiro_Fujimori
15 - Aurora
06-20-2024
04:45 PM
- 新着としてマーク
- ブックマーク
- 購読
- ミュート
- RSS フィードを購読する
- ハイライト
- 印刷
- モデレーターに通知する
やはり brute force しか思いつきませんでした。
なお、8,127の次の完全数は33,550,336だとWikipediaで聞いたので、
同じ処理で出せるか試してみたところ、30分経過時点で 125,696 までしか進まないので止めました。。
スポイラ
Workflow
AkimasaKajitani
17 - Castor
06-20-2024
04:48 PM
- 新着としてマーク
- ブックマーク
- 購読
- ミュート
- RSS フィードを購読する
- ハイライト
- 印刷
- モデレーターに通知する
@Yoshiro_Fujimori さん その発想はAoCの1日の後半の問題みたいですね!
gawa
16 - Nebula
06-20-2024
09:59 PM
- 新着としてマーク
- ブックマーク
- 購読
- ミュート
- RSS フィードを購読する
- ハイライト
- 印刷
- モデレーターに通知する
偶数の完全数の性質を使うと、次の完全数は比較的簡単に求められます。スポイラーにネタバレを書いておきます。
https://ja.wikipedia.org/wiki/%E5%AE%8C%E5%85%A8%E6%95%B0
スポイラ
Wikipediによると、「6以外の完全数は、1から連続する正の奇数の立方和で表せる」そうなので、天下りになりますが、検索対象をかなり制限することができます。