Project Euler : Problem4 『Largest palindrome product』

NOON / CarbonNYC [in SF!]

問題

　3桁どうしの掛け算で作られる、6桁かつ最大の回文数は何か。

Palindromic Number(回文数)？

　回文と同じで、123321みたいに右から読んでも左から読んでも同じ数字になるものを言う。
6桁の回文数 P を式で書けばこんな感じ。
\(P = 10^{5} a + 10^{4} b + 10^{3} c + 10^{2} c + 10 b + a\)
a,b,cは整数で、1 ≦ a ≦ 9、0 ≦ b,c ≦9の範囲。

　式を整理するとこんな感じになる。
\(P = (10^{5} + 1)a + (10^{4} + 10)b + (10^{3} + 10^{2})c\)
\(= 100001a + 10010b + 1100c\)
\(= 11 \times (9091a + 910b + 100c)\)
最後の式からわかることは、6桁の回文数は11の倍数だっていうことですね。

2桁やん！

　11の倍数だと分かったところで問題がでてくる。
与えられた問題の内容は3桁どうしの掛け算。
11は2桁……うーん、でも11で割れると分かってるしなぁ……。

11の倍数にしてしまおう

　後の9091a～が
\(9091a + 910b + 100c = x \times y\)
の形であれば、こうなる。
\(P = 11x \times y \)
与えられた問題は3桁どうしの掛け算なので、11xとyが3桁であればいい。
となると、xは10≦x≦90の範囲を調べればいい。
\(P \: mod \: 11x = 0\)
ある回文数Pを11xで割ったときに余りが0になったやつを選んで、
\( y = \frac{P}{11x}\)
次にyが3桁かどうか判定すればいいのか。

私の考えた方法

1. 6桁の回文数Pを大きいものから一つ選ぶ
2. Pが11のx倍(10≦x≦90)で割り切れるか試す
3. 割り切れるならP/(11x)が3桁かどうかチェックする
4. 3が通れば答えとしてPを出力する。
5. 通らなければ1に戻って次に大きい回文数を選ぶ

コード

using System;
using System.Diagnostics;

namespace Problem4
{
    class Program
    {
        static void Main(string[] args)
        {
            Debug.WriteLine(solv2());
        }

        static int solv2()
        {
            for(int c = 9; c >= 1; c--)
            {
                for(int d = 9; d >= 0; d--)
                {
                    for(int e = 9; e >= 0; e--)
                    {
                        int p = 100001 * c + 10010 * d + 1100 * e;

                        for(int x = 10; x <= 90; x++)
                        {
                            if(p%(11*x) == 0)
                            {
                                
                                if ((p / (11 * x)).ToString().Length == 3)
                                {
                                    return p;
                                }
                            }
                        }
                    }
                }
            }

            return 0;
        }
    }
}