読者です 読者をやめる 読者になる 読者になる

さんぽみち

なにか思いついたときとかに気まぐれに更新されます。

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の倍数になりそうな気はする?