yukicoder No747

No747

途中までc++で書いていたが、よくわからなくなったため、pythonで書き直してAC。

※コンテスト終了後に見直してみると、"285714"を"428571"にしたら通った。

まずはNを6で割った余りを求めて、それのk乗を求める。

1. Nの剰余

   今回のように64bit整数で扱える範囲を超える場合は、pythonのように多倍長整数を使える言語を使うと楽。しかし、c++で解くために考察してみた。

   6は「3の倍数」であり「2の倍数」なので、ここから考えてみた。

   6の剰余	3の剰余	2の剰余
   0	0	0
   1	1	1
   2	2	0
   3	0	1
   4	1	0
   5	2	1

   上の表を参考に考えると、

   n = input()

   ans = [[0, 4, 2], [3, 1, 5]][int(n[-1]) & 1][sum(int(i) for i in n) % 3]

   のようになる。

2. k乗

   繰り返し二乗法で解くのかと思ったが、そうでもなかった。

   xを0、または6の倍数のように、6の剰余が0の数と定義する。

   bを6の剰余と定義する。

   (x + b)^k

   ただし、1乗はその数自体なため、2乗3乗を考える。今回は0乗はないので、考えない。

   ①b == 0

   • (x + 0)^kは何乗しても、mod6=0である。

   ②b == 1

   • (x + 1)(x + 1) = (x² + 2x + 1)

     はmod6=1なため、何乗しても1になる。

   ③b == 2

   • (x + 2)(x + 2) = (x² + 4x + 4)

     2乗したら、mod6=4になった。

   • (x² + 4x + 4)　⇒　(x + 4)で3乗を計算。

     (x + 4)(x + 2) = (x² + 6x + 8)

     8はmod6=2なため、2に戻った。

     以上から、kが奇数の場合は2、偶数の場合は4になる。

   ④b == 3

   • (x + 3)(x + 3) = (x² + 6x + 9)

     9はmod6=3なため、何乗しても3になる。

   ⑤b == 4

   • (x + 4)(x + 4) = (x² + 8x + 16)

     16はmod6=4なため、何乗しても4になる。

   ⑥b == 5

   • (x + 5)(x + 5) = (x² + 10x + 25)

     2乗したら、mod6=1になった。

   • (x² + 10x + 25)　⇒　(x + 1)で3乗を計算。

     (x + 1)(x + 5) = (x² + 6x + 5)

     mod6=5に戻った。

     以上から、kが奇数の場合は5、偶数の場合は1になる。

   まとめると以下の表のようになる。

   	0	1	2	3	4	5
   1乗	0	1	2	3	4	5
   2乗	0	1	4	3	4	1
   3乗	0	1	2	3	4	5
   4乗	0	1	4	3	4	1
   5乗	0	1	2	3	4	5

   以上より、

   kが偶数で、Nの剰余が

   ①2⇒4

   ②5⇒1

   になる。