/*
2004/8 年子平方数
coded by Isaku WADA

 ┌─────────────────────────────┐
 │ 偶数桁の平方数(ある数を2乗してできる数)で、それぞれ同じ│
 │桁数になるように左右半分に割ったとき、その2つの数が連続し│
 │た2数になっているものを、「年子(としご)平方数」と呼ぶこと│
 │にする。たとえば、                    │
 │    8281(=91^2)                      │
 │では81と82が連続した2数となっている。ただし、右半分と│
 │左半分、どちらが大きくてもかまわない。ここでは正の整数のみ│
 │を扱い、すなおに10進法で考える。            │
 │ この「年子平方数」をほかにも見つけてほしいのだが、たくさ│
 │んあるので、小さいほうから順に(上記の例を含めて)21番目ま│
 │でをお答えいただきたい。                 │
 └─────────────────────────────┘
 ┌─────────────────────────────┐
 │・プログラムの説明                    │
 │                             │
 │ プログラムの第1パラメータとして、何番目の解まで計算する│
 │かを指定します。省略すると21になります。平方数の根を  │
 │unsigned longで保持しているので40番目の解まで計算できま │
 │す。第2パラメータとして、計算を何回繰り返すかを指定しま │
 │す。省略すると1回だけ計算します。            │
 │ 初期状態として平方数を16、その根rootを4とします。平方│
 │数は左半分をleft、右半分をrightとして表します。従ってleft │
 │の初期値は1、rightの初期値は6となります。変数mはleftの最│
 │小値を表し、nはその10倍の数を表します。mの初期値は1、n │
 │の初期値は10です。根の桁数が増えるごとにmとnは10倍され│
 │てゆきます。                       │
 │ leftがm以上ならば平方数は偶数桁なので、leftとrightが年子│
 │かどうか調べて、年子なら表示します。21番目の解を表示した│
 │ら、書き出しフラグを0にして、以降の繰り返しに解を表示しな│
 │いようにします。そして、Solve関数を終えます。       │
 │ rootが1増えると平方数は2*root-1だけ増えることを利用して│
 │、掛け算を避け、高速化しています。さらに高速化するために平│
 │方数の増分を記録する変数dxを別に用意し、rootが1増えるとdx│
 │が2増えるようにしています。そしてrootが1増えるごとに  │
 │rightをdxだけ増やします。この後、rightが右半分の最大値nを │
 │超えている間、leftを増やし、rightからnを引くこと繰り返しま│
 │す。                           │
 │ rootを増やしてnと等しくなったら、桁が増えたことになるの │
 │でmとnを10倍して、増えすぎたleftを10分の1にします。 │
 ├─────────────────────────────┤
 │・感想                          │
 │                             │
 │ 最初は平方数を左右に分けずに、一まとめに計算しようとしま│
 │した。doubleの精度は17桁であり、21番目の平方数には精度│
 │が不足したため、多倍長整数のプログラムを組んでいました。特│
 │に多倍長の掛け算に時間がかかっていました。        │
 │ 平方数を左右に分けて処理したところ、多倍長整数のプログラ│
 │ムが不要になったために、かなりすっきりしたソースになり、同│
 │時に高速になりました。                  │
 │ しかし、おまけの問題の4番目の解を計算するのに、良い計算│
 │方法が思いつかず、2時間36分もかかってしまいました。  │
 └─────────────────────────────┘
 ┌──────────────┬────┬───────┐
 │コンパイラ         │実行時間│ファイルサイズ│
 ├──────────────┼────┼───────┤
 │Microsoft Visual C++ 6.0  │1.453 秒│ 49512 byte │
 │Microsoft Visual C++ 2003  │1.375 秒│ 45056 byte │
 │Borland C++ 5.5.1 for Win32 │1.625 秒│ 52736 byte │
 │gcc-2.953(djgpp)      │1.758 秒│ 107845 byte │
 │gcc-2.953(cygwin)      │1.703 秒│ 19068 byte │
 │LSI C-86 Ver 3.30 試食版  │8.670 秒│ 13258 byte │
 │Turbo C Ver 1.5(small model)│7.420 秒│ 10778 byte │
 ├──────────────┼────┴───────┤
 │ CPU:Pentium4 2.52GHz │ OS:Windows XP   │
 └──────────────┴────────────┘
*/

#include <stdio.h>
#include <stdlib.h>
#include <time.h>

void Solve(int sol)
{
    unsigned long m=1,n=10,root=4,left=1,right=6,dx=2*root-1;
    int count=0;

    for (;;) {
        if (left>=m&&(left+1==right||right+1==left)) {
            printf("%d %lu %lu%lu\n",++count,root,left,right);
            if (count>=sol) return;
        }
        root++; dx+=2; right+=dx;
        while (right>=n) { left++; right-=n; }
        if (root==n) { left=m; m=n; n*=10; }
    }
}

/*┌────────────────────┐
 │MS-DOS コンパイラ用のシンプルな clock() │
 └────────────────────┘*/
#if CLOCKS_PER_SEC == 1
#undef CLOCKS_PER_SEC
#endif
#ifndef CLOCKS_PER_SEC
#define CLOCKS_PER_SEC 1000
#include <dos.h>
static long clock(void) {
    union REGS t; t.h.ah=0x2c; intdos(&t,&t);
    return t.h.dl*10L+t.h.dh*1000L+t.h.cl*60000L+t.h.ch*3600000L;
}
#endif

int main(int argc,char*argv[])
{
    double StartTime=clock(); int i,num,sol;

    if (argc>1) sol=atoi(argv[1]); else sol=21;
    if (argc>2) num=atoi(argv[2]); else num=1;
    for (i=0;i<num;i++) Solve(sol);
    printf("実行時間 %.3f 秒\n",(clock()-StartTime)/CLOCKS_PER_SEC);
    return EXIT_SUCCESS;
}