法による計算

10 進数の自然数 n（1 ≦ n ≦ 10¹⁰）に対して，16 進数の A を n 個並べた数を F(n) と定義する。
F(n) を 10 進数で表したものを 10⁶ で割った余りを出力する。

例えば，F(10) を 10 進数で表すと 733007751850 で，この数を 10⁶ で割った余りは 751850 である。

> fun = function(n) {
+     ans = 10
+     n = (n-2) %% 3125
+     if (n >= 0) {
+         for (i in 0:n) {
+             ans = (ans*16 + 10) %% 1e6
+         }
+     }
+     ans
+ }

> fun(10)
[1] 751850
> fun(9999999999)
[1] 462890

 

ヒント: 1e6 の剰余って，実際の値には限りがある。1e6 通りもあるわけでもない。