問題
projecteuler.net
日本語訳→http://www.odz.sakura.ne.jp/projecteuler/index.php?cmd=read&page=Problem%2052
6倍した時桁上がりしない最上位桁
6倍した時に1倍と同じ数字が使われているということは、最上位桁が桁上がりしない事と同じ意味。
仮に最上位桁が2だとすると、2×6=12で桁上がりするのでダメ。
2未満というと1しかないので、最上位桁は1
6倍した時に全体の桁が増えない最上位桁の次の桁
1?…×6の時に最上位桁が桁上がりしないような?の最大値を知りたい。
仮に?が6だと16…×6=96…でいけるが、17×6は102…となってしまうことから?の最大値は6以下。
上限を求める
16…x6=96…より、次の桁は6倍した時桁上がりしないように40未満になってほしい。
ということは6が最大値なので、値は166…になる。
見て分かるように以降6が続くので166…6が調べる上限。
下限を調べる
探索の下限として1…を考える。
トップに1が含まれるということは、2~6倍するために桁のどこかに2~6が含まれないといけないはず。
つまり123456の6桁から探索を始めるべき…?(自信ない)
探索範囲の遷移は
123456~166666→1123456~1666666という感じに変わっていく。
C#でのintの最大値
int.MaxValueは2147483647で10桁あるからまぁ大丈夫でしょう多分。
同じ数字が使われているか確認する方法
値を文字列化→char配列化→ソート→SequenceEqualで判定
もっといい方法があるかも。
コード
using System; using System.Diagnostics; using System.Linq; namespace eu { class Program { static void Main(string[] args) { Stopwatch sw = new Stopwatch(); sw.Start(); Problem52(); sw.Stop(); Console.WriteLine($"Time {sw.ElapsedMilliseconds}"); } private static void Problem52() { int startNum = 123456; int addNum = 100000; int maxNum = 166666; for (int i = startNum; i <= maxNum; i++) { var s1 = i.ToString().ToCharArray(); var s2 = (i * 2).ToString().ToCharArray(); var s3 = (i * 3).ToString().ToCharArray(); var s4 = (i * 4).ToString().ToCharArray(); var s5 = (i * 5).ToString().ToCharArray(); var s6 = (i * 6).ToString().ToCharArray(); Array.Sort(s1); Array.Sort(s2); Array.Sort(s3); Array.Sort(s4); Array.Sort(s5); Array.Sort(s6); if (s1.SequenceEqual(s2) & s3.SequenceEqual(s4) & s5.SequenceEqual(s6)) { if (s2.SequenceEqual(s3) & s4.SequenceEqual(s5)) { Console.WriteLine($"{i}"); Console.WriteLine($"{i * 2}"); Console.WriteLine($"{i * 3}"); Console.WriteLine($"{i * 4}"); Console.WriteLine($"{i * 5}"); Console.WriteLine($"{i * 6}"); break; } } if (i == maxNum) { //初期値の更新 addNum = addNum * 10; startNum = startNum + addNum - 1; //最大値の更新 maxNum = maxNum * 10 + 6; } } } } }