C#で Project Euler P4
問題
左右どちらから読んでも同じ値になる数を回文数という. 2桁の数の積で表される回文数のうち, 最大のものは 9009 = 91 × 99 である.
では, 3桁の数の積で表される回文数の最大値を求めよ.
Problem 4 - PukiWiki
解答
using System; public static class P4 { public static void Main() { Console.WriteLine(Calc()); } private static long Calc() { int ret = 0; for(int i = 999; i > 100; i--) { for(int j = 999; j > 100; j--) { string s = (i * j).ToString(); Console.WriteLine(i * j); if(IsRenum(i * j)) { Console.WriteLine(i + ", " + j); ret = i * j; goto End; } } } End: return ret; } private static bool IsRenum(int num) { var re = 0; for(var work = num; work > 0; work /= 10) { re = re * 10 + work % 10; } return re == num; } }
計算量 $O(n^2\log n)$
やり方が思い付かなかったので愚直に総当たりしました。
回文数の性質を調べればもっと計算量抑えられそう。
調べてないけど、直観的に11の倍数になりそうな気はする?