Cマガ電脳クラブ(第093回) 端数よりダンゴ

問題

0ではない数字 (1〜9) をふたつ選び、これらをX、Yとしておく。
このX、Yの間に何個かの(1個以上)0を挟み込み、
　X000・・・00Y
という数を考えたときに、この数がYXという数で割りきれるものを探してほしい。

たとえば、
 300001/13=2307
となる。

ここで、ある数X、Yの間には、割り切れるのに必要な最小の個数の0を挟むこと、
と約束すると、0の数が最長になるX、Yは何だろうか。

ソース

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    struct AnswerKouhoDef
    {
        internal int X;
        internal int Y;
        internal int ZeroCnt;
    }

    static void Main()
    {
        var AnswerKouhoList = new List<AnswerKouhoDef>();

        for (int X = 1; X <= 9; X++) {
            for (int Y = 1; Y <= 9; Y++) {
                bool HasAnswer; int ZeroCnt;
                DeriveZeroCnt(X, Y, out HasAnswer, out ZeroCnt);

                if (HasAnswer == false) {
                    Console.WriteLine("X={0},Y={1}の場合、割り切れません", X, Y);
                    continue;
                }
                Console.WriteLine("X={0},Y={1}の場合、0の数={2}", X, Y, ZeroCnt);
                AnswerKouhoDef WillAdd;
                WillAdd.X = X; WillAdd.Y = Y;
                WillAdd.ZeroCnt = ZeroCnt;
                AnswerKouhoList.Add(WillAdd);
            }
        }

        int AnswerZeroCnt = AnswerKouhoList.Max(X => X.ZeroCnt);
        AnswerKouhoList.RemoveAll(X => X.ZeroCnt < AnswerZeroCnt);
        AnswerKouhoList.ForEach(
            A => Console.WriteLine("答えは、X={0},Y={1}の時で、0の数={2}", A.X, A.Y, A.ZeroCnt));
    }

    //割り切れるのに必要な0の数を求める
    static void DeriveZeroCnt(int pX, int pY, out bool pHasAnswer, out int pZeroCnt)
    {
        pHasAnswer = false; pZeroCnt = 1;
        int Hou = 10 * pY + pX;

        int ProdMod = (pX * 100) % Hou;
        var ProdModList = new List<int>() { ProdMod };

        while (true) {
            if ((pY + ProdMod) % Hou == 0) {
                pHasAnswer = true;
                return;
            }

            ProdMod = (ProdMod * 10) % Hou;
            if (ProdModList.Contains(ProdMod)) return;

            ProdModList.Add(ProdMod);
            pZeroCnt++;
        }
    }
}

実行結果

省略
X=8,Y=7の場合、割り切れません
X=8,Y=8の場合、0の数=2
X=8,Y=9の場合、割り切れません
X=9,Y=1の場合、0の数=16
X=9,Y=2の場合、0の数=26
X=9,Y=3の場合、0の数=4
X=9,Y=4の場合、0の数=40
X=9,Y=5の場合、0の数=56
X=9,Y=6の場合、0の数=20
X=9,Y=7の場合、0の数=11
X=9,Y=8の場合、0の数=42
X=9,Y=9の場合、0の数=2
答えは、X=7,Y=9の時で、0の数=94

解説

合同式の公式
(A*B) mod C = ((A mod C) * B) mod C
を使ってます。