川添さん問題01 カット・アンド・スクエア

■■■問題■■■

偶数 n に対して、先頭にゼロを持たない n 桁の整数で、次の条件を満たすものを考えましょう。

【条件】
この数を上 n/2 桁と下 n/2 桁とに分け、それぞれを2乗して和をとると、元の数に戻る。

例えば n = 4 の場合は、1233 と 8833 がこの条件を満たします。
　12*12 ＋ 33*33 ＝ 1233
　88*88 ＋ 33*33 ＝ 8833

なお、下 n/2 桁の数が先頭にゼロを持つときは、余計な先頭のゼロを取り除いて考えて下さい。
(例：020 → 20、0000 → 0)
例えば 9805 に対しては 98*98 ＋ 5*5 という計算を行うことになります。

n=4 の場合にこの条件を満たす数は 1233 と 8833 の二つのみです。これらの総和は 10066 です。

■ 第1問 (Normal)
n=6 の場合にこの条件を満たす数はただ一つ存在します。この数を求めてください。

■ 第2問 (Hard)
n=10 の場合にこの条件を満たす全ての数の総和を求めてください。

C#のソース

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

class Program
{
    static void Main()
    {
        var sw = System.Diagnostics.Stopwatch.StartNew();

        long[] NArr = { 4, 6, 10 };

        foreach (long EachN in NArr) {
            List<long> AnswerList = DeriveAnswerList(EachN);
            Console.WriteLine("N={0}での解は", EachN);
            AnswerList.ForEach(A => Console.WriteLine(A));
            Console.WriteLine("合計は{0}", AnswerList.Sum());
            Console.WriteLine();
        }
        Console.WriteLine("経過時間={0}", sw.Elapsed);
    }

    static List<long> DeriveAnswerList(long pN)
    {
        var WillReturn = new List<long>();

        long UeMin = Derive10Bekijyou(pN / 2 - 1);
        long UeMax = Derive10Bekijyou(pN / 2) - 1;

        for (long CurrUe = UeMin; CurrUe <= UeMax; CurrUe++) {
            long wkC = CurrUe * (CurrUe - UeMax - 1);
            List<long> AnswerShitaList = Solve2JiHouteishiki(1, -1, wkC);

            AnswerShitaList.RemoveAll(A => A > UeMax);
            if (AnswerShitaList.Count > 0) {
                AnswerShitaList.ForEach(
                    A => WillReturn.Add((long)CurrUe * CurrUe + (long)A * A));
            }
        }

        return WillReturn;
    }

    //10のべき乗を求める
    static long Derive10Bekijyou(long pJyousuu)
    {
        long WillReturn = 1;
        for (long I = 1; I <= pJyousuu; I++)
            WillReturn *= 10;
        return WillReturn;
    }

    //2次方程式の解を返す
    static List<long> Solve2JiHouteishiki(long pA, long pB, long pC)
    {
        var WillReturn = new List<long>();
        long LongHanbetuShiki = pB * pB - 4 * pA * pC;

        //実数解を持たない場合
        if (LongHanbetuShiki < 0) return WillReturn;

        //平方数でない場合
        double DoubleHanbetuShiki = (double)LongHanbetuShiki;
        long wkSqrt = (long)(Math.Truncate(Math.Sqrt(DoubleHanbetuShiki)));
        if (wkSqrt * wkSqrt != LongHanbetuShiki) return WillReturn;

        WillReturn.Add((-pB + wkSqrt) / (2 * pA));
        WillReturn.Add((-pB - wkSqrt) / (2 * pA));

        //負数は不可
        WillReturn.RemoveAll(X => X < 0);

        //重解ならDistinct
        if (LongHanbetuShiki == 0) WillReturn = WillReturn.Distinct().ToList();

        return WillReturn;
    }
}

C#の実行結果

N=4での解は
1233
8833
合計は10066

N=6での解は
990100
合計は990100

N=10での解は
1765038125
2584043776
7416043776
8235038125
9901009901
合計は29901173703

経過時間=00:00:00.1310222

C++のソース

#include <iostream>
#include <math.h>
#include <stdio.h>
#include <vector>
#include <windows.h>

std::vector<long long> DeriveAnswerVect(long long pN);
long long Derive10Bekijyou(long long pJyousuu);
std::vector<long long> Solve2JiHouteishiki(long long pA,long long pB,long long pC);

void OutDate()
{
    SYSTEMTIME stTime;
    GetLocalTime(&stTime);
    char strTime[100];
    wsprintf(strTime , "日時は、%4d年%2d月%2d日%02d時%02d分%02d秒" ,
        stTime.wYear , stTime.wMonth , stTime.wDay ,
        stTime.wHour , stTime.wMinute , stTime.wSecond);
    std::cout << strTime << std::endl;
}

void main()
{
    OutDate();
    long long NArr[]={4,6,10};
    int UB = sizeof(NArr)/sizeof(NArr[0])-1;

    for(int I=0;I<=UB;I++){
        std::vector<long long> AnswerVect = DeriveAnswerVect(NArr[I]);
        printf("N=%lldでの解は\n", NArr[I]);
        long long SumVal=0;
        for(int J=0;J<=(int)AnswerVect.size()-1;J++){
            printf("%lld\n",AnswerVect.at(J));
            SumVal+=AnswerVect.at(J);
        }
        printf("合計は%lld\n",SumVal);
        puts("");
    }
    OutDate();
}

std::vector<long long> DeriveAnswerVect(long long pN)
{
    std::vector<long long> WillReturn;

    long long UeMin = Derive10Bekijyou(pN / 2 - 1);
    long long UeMax = Derive10Bekijyou(pN / 2) - 1;

    for (long long CurrUe = UeMin; CurrUe <= UeMax; CurrUe++) {
        long long wkC = CurrUe * (CurrUe - UeMax - 1);
        std::vector<long long> AnswerShitaVect = Solve2JiHouteishiki(1, -1, wkC);

        if ((int)AnswerShitaVect.size() > 0) {
            for(int I=0;I<=(int)AnswerShitaVect.size()-1;I++){
                if(AnswerShitaVect.at(I) > UeMax) continue;
                WillReturn.push_back((long long)CurrUe * CurrUe 
                    + (long long)AnswerShitaVect.at(I) * AnswerShitaVect.at(I));
            }
        }
    }
    return WillReturn;
}

//10のべき乗を求める
long long Derive10Bekijyou(long long pJyousuu)
{
    long long WillReturn = 1;
    for (long long I = 1; I <= pJyousuu; I++)
        WillReturn *= 10;
    return WillReturn;
}

//2次方程式の解を返す
std::vector<long long> Solve2JiHouteishiki(long long pA,long long pB,long long pC)
{
    std::vector<long long> WillReturn;
    long long LongHanbetuShiki = pB * pB - 4 * pA * pC;

    //実数解を持たない場合
    if (LongHanbetuShiki < 0) return WillReturn;

    //平方数でない場合
    double DoubleHanbetuShiki = (double)LongHanbetuShiki;
    long long wkSqrt = (long long)sqrt(DoubleHanbetuShiki);
    if (wkSqrt * wkSqrt != LongHanbetuShiki) return WillReturn;

    long long WillAdd1 = (-pB + wkSqrt) / (2 * pA);
    long long WillAdd2 = (-pB - wkSqrt) / (2 * pA);

    if(WillAdd1 >=0){ //負数は不可
        WillReturn.push_back(WillAdd1);
    }
    if(WillAdd2 >=0){ //負数は不可
        if(WillAdd1 != WillAdd2) //重解なら除外
            WillReturn.push_back(WillAdd2);
    }
    return WillReturn;
}

解説

n=4の場合
上2桁をA、下2桁をBとすると
A*A + B*B = A*100 + B を満たすのが必要条件です。
Aをループさせつつ、Bの2次方程式を解いてから、
十分性のチェックとして、Bが実数で99以下であることをチェックしてます。

計算量のオーダーは10の(n/2)乗となります。