結果

問題 No.3006 ベイカーの問題
ユーザー NP
提出日時 2025-02-02 22:26:37
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 47 ms / 2,000 ms
コード長 651 bytes
コンパイル時間 619 ms
コンパイル使用メモリ 82,432 KB
実行使用メモリ 52,736 KB
最終ジャッジ日時 2025-02-02 22:26:40
合計ジャッジ時間 3,180 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

MOD=998244353
def modinv(x):
   return pow(x,MOD-2,MOD)
def add(a,b):  
   return((a[0]+b[0])%MOD,(a[1]+b[1])%MOD)
def sub(a,b):
   return((a[0]-b[0])%MOD,(a[1]-b[1])%MOD)
def mul(a,b):
   return((a[0]*b[0]-5*a[1]*b[1])%MOD,(a[0]*b[1]+a[1]*b[0])%MOD)
def inv(a):
   u,v=a;n=(u*u+5*v*v)%MOD;return(u*modinv(n)%MOD,(-v)*modinv(n)%MOD)
def power(a,e):
    r=(1,0)
    b=a
    while e:
        if e&1: r=mul(r,b)
        b=mul(b,b)
        e//=2
    return r
a,b,N=map(int,input().split())
a,b=a%MOD,b%MOD
A=(a,b)
if A==(1,0):
  print(N%MOD,0)
else:
    p=power(A,N+1)
    num=sub(p,A)
    denom=inv(sub(A,(1,0)))
    S=mul(num,denom)
    print(S[0],S[1])
0