結果
問題 |
No.344 ある無理数の累乗
|
ユーザー |
![]() |
提出日時 | 2016-02-14 19:33:58 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 133 ms / 2,000 ms |
コード長 | 1,281 bytes |
コンパイル時間 | 2,022 ms |
コンパイル使用メモリ | 77,868 KB |
実行使用メモリ | 54,348 KB |
最終ジャッジ日時 | 2024-09-22 06:36:34 |
合計ジャッジ時間 | 6,883 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 30 |
ソースコード
import java.util.Scanner; class BiMtx { int a,b,c,d; void set(int p, int q, int r, int s){ a=p; b=q; c=r; d=s; } void set(BiMtx A){ a = A.a; b = A.b; c = A.c; d = A.d; } BiMtx (int p, int q, int r, int s){ set(p,q,r,s); } } class BiMtxPow { BiMtx BMmulti (BiMtx A, BiMtx B){ BiMtx C = new BiMtx(0,0,0,0); C.a = (A.a * B.a + A.b * B.c) % 1000; C.b = (A.a * B.b + A.b * B.d) % 1000; C.c = (A.c * B.a + A.d * B.c) % 1000; C.d = (A.c * B.b + A.d * B.d) % 1000; return C; } BiMtx BMpow (BiMtx A, long n){ BiMtx C = new BiMtx(0,0,0,0); BiMtx half = new BiMtx(0,0,0,0); if(n == 0){ C.set(1, 0, 0, 1); return C; }else if (n == 1){ C.set(A); return C; }else if((n>>1)<<1 == n){ half = BMpow(A,(n>>1)); return BMmulti(half,half); }else{ half = BMpow(A,(n>>1)); return BMmulti(half,BMmulti(half,A)); } } } class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); long n = sc.nextLong(); sc.close(); BiMtx A = new BiMtx(0,1,2,2); BiMtx C = new BiMtx(0,0,0,0); BiMtxPow bmp = new BiMtxPow(); C = bmp.BMmulti(A, A); C = bmp.BMpow(A, n); if(n%2==0)System.out.println((2*C.a + 2* C.b -1) % 1000); else System.out.println((2*C.a + 2* C.b) % 1000); } }