問題一覧 > 通常問題

No.1595 The Final Digit

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

問題文

次のように定義される数列 A=(A1,A2,A3,…,AK) を考えます。

  • A1=p,A2=q,A3=r である。
  • N≥4 では、AN=AN−1+AN−2+AN−3 である。
整数 p,q,r,K が与えられるので、AK を十進法で表したときの 1 の位を求めてください。

入力

p q r K

出力

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

制約

  • 1≤p≤109
  • 1≤q≤109
  • 1≤r≤109
  • 4≤K≤1018
  • 入力はすべて整数

サンプル

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

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

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

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