トップページに戻る
次のC#のサンプルへ
前のC#のサンプルへ
Cマガ電脳クラブ(第069回) 割り切れ魔数?
問題
3816547290
この大町数 (0から9までの10個の数字が1度ずつ登場する数) は、
おもしろいことに左端からN桁を切り出したとき、その数がNで割り切れる。
たとえば3816は4で,3816547は7で割り切れるのだ。
このような大町数はこれひとつしかない。
さて、今回は「大町」の条件を取り外してみよう。
つまり、「どこにどんな数字を使ってもよい」ということにしたら、
「左端からN桁を切り出した数が、いつもNで割り切れる数」はどこまで大きくできるだろうか。
ここでは、10進法以外は考えないことにする。
ソース
using System;
using System.Collections.Generic;
using System.Linq;
class Program
{
struct JyoutaiDef
{
internal int KetaSuu;
internal int[] ValArr;
}
static void Main()
{
var stk = new Stack<JyoutaiDef>();
JyoutaiDef WillPush;
WillPush.KetaSuu = 1;
for (int I = 1; I <= 9; I++) {
WillPush.ValArr = new int[] { I };
stk.Push(WillPush);
}
int MaxKeta = 0;
while (stk.Count > 0) {
JyoutaiDef Popped = stk.Pop();
if (MaxKeta <= Popped.KetaSuu) {
MaxKeta = Popped.KetaSuu;
var sb = new System.Text.StringBuilder();
Array.ForEach(Popped.ValArr, X => sb.Append(X));
Console.WriteLine("{0}桁の解{1}を発見", Popped.KetaSuu, sb.ToString());
}
for (int I = 0; I <= 9; I++) {
WillPush.KetaSuu = Popped.KetaSuu + 1;
WillPush.ValArr = Popped.ValArr.Concat(new int[] { I }).ToArray();
if (IsBaisuu(WillPush.ValArr, WillPush.KetaSuu))
stk.Push(WillPush);
}
}
}
static bool IsBaisuu(int[] pValArr, int pWarukazu)
{
//余りの法則その1 (A+B)%C = A%C + B%C
//余りの法則その2 (A*B)%C = (A%C) * (B%C)
int SumVal = 0;
for (int I = 0; I <= pValArr.GetUpperBound(0); I++) {
SumVal *= 10;
SumVal += pValArr[I];
SumVal %= pWarukazu;
}
return SumVal == 0;
}
}
実行結果
省略
20桁の解96685896604836004260を発見
21桁の解966858966048360042609を発見
22桁の解9668589660483600426096を発見
22桁の解9068584050968400006092を発見
22桁の解8468047260244656728072を発見
22桁の解7412580810843600420006を発見
22桁の解7264565640241056724082を発見
23桁の解72645656402410567240820を発見
23桁の解40285216807290082800921を発見
24桁の解402852168072900828009216を発見
24桁の解360852885036840078603672を発見
25桁の解3608528850368400786036725を発見
解説
余りの法則その1 (A+B)%C = A%C + B%C
余りの法則その2 (A*B)%C = (A%C) * (B%C)
を使って、余りを求めてます。
Decimal型を使用したソースは、第130回 こだ割り数で扱ってます。
(第069回と第130回は、同じ問題であるため)