問題一覧 > 通常問題

No.1595 The Final Digit

レベル : / 実行時間制限 : 1ケース 2.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : / 解いたユーザー数 297
作問者 : e869120e869120 / テスター : hirakich1000000007hirakich1000000007 ygussanyygussany
6 ProblemId : 6417 / 出題時の順位表 / 自分の提出
問題文最終更新日: 2021-07-08 23:25:30

問題文

次のように定義される数列 $A = (A_1, A_2, A_3, \dots, A_K)$ を考えます。

  • $A_1 = p, A_2 = q, A_3 = r$ である。
  • $N \geq 4$ では、$A_N = A_{N-1} + A_{N-2} + A_{N-3}$ である。
整数 $p, q, r, K$ が与えられるので、$A_K$ を十進法で表したときの $1$ の位を求めてください。

入力

$p$ $q$ $r$ $K$

出力

答えを出力してください。

制約

  • $1 \leq p \leq 10^9$
  • $1 \leq q \leq 10^9$
  • $1 \leq r \leq 10^9$
  • $4 \leq K \leq 10^{18}$
  • 入力はすべて整数

サンプル

サンプル1
入力
11 11 11 7
出力
7

$A_7 = 187$ であるため、$7$ と出力すれば正解となります。

サンプル2
入力
86 91 20 1001
出力
8
サンプル3
入力
31415 92653 58979 1000000000000000000
出力
5

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。