Problem95 友愛鎖

問題

ある数の真の約数とは, それ自身を除く約数すべてである.
例えば, 28 の真の約数は 1, 2, 4, 7, 14 である.
これらの約数の和は 28 に等しいため, これを完全数と呼ぶ.

面白いことに, 220 の真の約数の和は 284 で, 284 の真の約数の和は 220 となっており,
二つの数が鎖をなしている. このため, 220 と 284 は友愛数と呼ばれる.

さらに長い鎖はあまり知られていないだろう.
例えば, 12496 から始めると, 5 つの数の鎖をなす.

12496 → 14288 → 15472 → 14536 → 14264 → 12496 → ...

この鎖は出発点に戻っているため, 友愛鎖と呼ばれる.

いずれの要素も 1000000 を超えない最長の友愛鎖の最小のメンバーを求めよ.

ソース

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

class Program
{
    const int Jyougen = 1000000 - 1;
    static int MaxChainLength = 1;

    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();
        var AnswerValSet = new HashSet<int>();

        for (int I = 1; I <= Jyougen; I++) {
            if (I % 100000 == 1)
                Console.WriteLine("I={0},MaxChainLength={1},経過={2}", I, MaxChainLength, sw.Elapsed);

            List<int> ChainList = DeriveChain(I);
            if (ChainList == null) continue;
            int ChainLength = ChainList.Count;

            if (MaxChainLength < ChainLength) { //鎖の最長を更新した場合
                MaxChainLength = ChainLength;
                AnswerValSet.Clear();
                AnswerValSet.Add(ChainList.Min());
            }
            if (MaxChainLength == ChainLength) { //鎖の最長とタイの場合
                AnswerValSet.Add(ChainList.Min());
            }
        }

        Console.Write("答えは、");
        int[] AnswerArr = AnswerValSet.OrderBy(X => X).ToArray();
        for (int I = 0; I <= AnswerArr.GetUpperBound(0); I++) {
            Console.Write("{0}", AnswerArr[I]);
            if (I < AnswerArr.GetUpperBound(0)) Console.Write(",");
            else Console.WriteLine();
        }
    }

    static int[] mRestLengthArr = new int[Jyougen + 1];

    //鎖を求める
    static List<int> DeriveChain(int pTarget)
    {
        var ValList = new List<int>() { pTarget };
        int CurrVal = pTarget;

        while (true) {
            int NextVal = DeriveYakusuuSum(CurrVal);

            //上限を超えた場合
            if (Jyougen < NextVal) {
                mRestLengthArr[pTarget] = ValList.Count;
                return null;
            }

            //残りの鎖の長さで下限値枝切り
            if (mRestLengthArr[NextVal] != 0 &&
                ValList.Count + mRestLengthArr[NextVal] < MaxChainLength) {
                return null;
            }

            //出発点に戻った場合
            if (NextVal == pTarget) {
                mRestLengthArr[pTarget] = ValList.Count;
                return ValList;
            }

            //0に到着した場合
            if (NextVal == 0) {
                mRestLengthArr[pTarget] = ValList.Count;
                return null;
            }

            //ループした場合
            if (ValList.Contains(NextVal)) {
                mRestLengthArr[pTarget] = ValList.Count;
                return null;
            }

            ValList.Add(NextVal);
            CurrVal = NextVal;
        }
    }

    //真の約数の和を求める
    static int[] mYakusuuSumArr = new int[Jyougen + 1];
    static int DeriveYakusuuSum(int pTarget)
    {
        if (pTarget == 1) return 0;
        if (mYakusuuSumArr[pTarget] != 0) return mYakusuuSumArr[pTarget];

        int WillReturn = 0;
        for (int I = 1; I * I <= pTarget; I++) {
            if (pTarget % I == 0) {
                WillReturn += I;
                if (I != 1) { //約数が1でない場合は、ペアの約数を求める
                    int PairVal = pTarget / I;
                    if (PairVal != I) WillReturn += PairVal;
                }
                if (Jyougen < WillReturn) return WillReturn;
            }
        }
        return mYakusuuSumArr[pTarget] = WillReturn;
    }
}

実行結果

I=1,MaxChainLength=1,経過=00:00:00.0002349
I=100001,MaxChainLength=28,経過=00:00:00.2280672
I=200001,MaxChainLength=28,経過=00:00:00.5218811
I=300001,MaxChainLength=28,経過=00:00:00.8530930
I=400001,MaxChainLength=28,経過=00:00:01.1940366
I=500001,MaxChainLength=28,経過=00:00:01.5481576
I=600001,MaxChainLength=28,経過=00:00:01.9146693
I=700001,MaxChainLength=28,経過=00:00:02.2887456
I=800001,MaxChainLength=28,経過=00:00:02.6578917
I=900001,MaxChainLength=28,経過=00:00:03.0268196
答えは、14316

解説

真の約数を求めるメソッドでは、
対象数の1から平方根までのForループで試し割りして、
約数だったらペアの約数を求めることにより、
処理のオーダーをNからルートNに大きく減らしてます。

Cマガ電脳クラブ(第026回) 社交鎖