結果
問題 | No.344 ある無理数の累乗 |
ユーザー | prime_mgm |
提出日時 | 2016-02-14 19:33:58 |
言語 | Java21 (openjdk 21) |
結果 |
AC
|
実行時間 | 134 ms / 2,000 ms |
コード長 | 1,281 bytes |
コンパイル時間 | 2,403 ms |
コンパイル使用メモリ | 77,476 KB |
実行使用メモリ | 57,772 KB |
最終ジャッジ日時 | 2023-10-22 05:18:09 |
合計ジャッジ時間 | 7,120 ms |
ジャッジサーバーID (参考情報) |
judge9 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 130 ms
57,600 KB |
testcase_01 | AC | 129 ms
57,476 KB |
testcase_02 | AC | 133 ms
57,600 KB |
testcase_03 | AC | 132 ms
57,756 KB |
testcase_04 | AC | 129 ms
57,256 KB |
testcase_05 | AC | 129 ms
57,136 KB |
testcase_06 | AC | 129 ms
57,264 KB |
testcase_07 | AC | 131 ms
57,528 KB |
testcase_08 | AC | 131 ms
57,508 KB |
testcase_09 | AC | 131 ms
57,744 KB |
testcase_10 | AC | 133 ms
57,244 KB |
testcase_11 | AC | 131 ms
57,524 KB |
testcase_12 | AC | 130 ms
57,196 KB |
testcase_13 | AC | 132 ms
57,384 KB |
testcase_14 | AC | 121 ms
56,180 KB |
testcase_15 | AC | 133 ms
57,764 KB |
testcase_16 | AC | 133 ms
57,760 KB |
testcase_17 | AC | 132 ms
57,604 KB |
testcase_18 | AC | 134 ms
57,600 KB |
testcase_19 | AC | 133 ms
57,772 KB |
testcase_20 | AC | 134 ms
57,592 KB |
testcase_21 | AC | 134 ms
57,588 KB |
testcase_22 | AC | 133 ms
57,660 KB |
testcase_23 | AC | 131 ms
57,556 KB |
testcase_24 | AC | 132 ms
57,484 KB |
testcase_25 | AC | 134 ms
57,504 KB |
testcase_26 | AC | 134 ms
57,544 KB |
testcase_27 | AC | 131 ms
57,472 KB |
testcase_28 | AC | 130 ms
57,480 KB |
testcase_29 | AC | 132 ms
57,512 KB |
ソースコード
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); } }