朝日新聞2006年10月27日パズル横丁解答

プログラムの実行結果は以下の通り。

656

プログラムのソースは以下の通り。大きな勘違いをしていた。

#include "puzutl.h"

int             M, N, P;

const int S = 1000;

int pow6( int n)                // 6**n
{
  int s = 6;
  for( int i=1; i< n; i++) {
    s           *= 6;
    s           %= S;           // OverFlowを避けるため下3桁のみ
  }
  s             %= N;           // 循環をさぼる
  return    s;
}

int pow3( int n, int m)         // n**m
{
  int           v = 1;
  while( m--> 0) {
    v           = v * n;
    v           %= S;       // 下3桁のみ
  }
  return    v;
}

int main( int argc, cstring argv[])
{
  //--------------------------------------------------------------------
  // 6x6x6x… の循環を見つける。
  //--------------------------------------------------------------------
  int           num = 6;        // 初期値
  int           loop[S+1] = {0};
  for( int i=1; i< S; i++) {
    num         *= 6;
    num         %= S;       // 下三桁だけを調べて循環を探す
    if( loop[num]) {            // 循環発見
      M         = loop[num];
      N         = i-loop[num];
      break;
    }
    loop[num]   = i;            // 循環発見用に印を付ける
  }
  int p = pow6( pow6( pow6( pow6( pow6( 6)))));
  int x = pow3( 6, p);          // 下3桁のみの6**p
  ps( "%d\n", x);
  return    0;
}