結果

問題 No.344 ある無理数の累乗
ユーザー 37zigen37zigen
提出日時 2016-02-13 11:53:00
言語 Java21
(openjdk 21)
結果
AC  
実行時間 141 ms / 2,000 ms
コード長 1,760 bytes
コンパイル時間 4,508 ms
コンパイル使用メモリ 77,804 KB
実行使用メモリ 54,412 KB
最終ジャッジ日時 2024-09-22 06:13:30
合計ジャッジ時間 8,261 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 132 ms
53,944 KB
testcase_01 AC 141 ms
54,300 KB
testcase_02 AC 127 ms
54,028 KB
testcase_03 AC 128 ms
54,352 KB
testcase_04 AC 132 ms
54,296 KB
testcase_05 AC 130 ms
53,996 KB
testcase_06 AC 129 ms
54,012 KB
testcase_07 AC 132 ms
53,876 KB
testcase_08 AC 131 ms
54,296 KB
testcase_09 AC 133 ms
54,188 KB
testcase_10 AC 130 ms
54,412 KB
testcase_11 AC 131 ms
53,932 KB
testcase_12 AC 120 ms
53,140 KB
testcase_13 AC 129 ms
54,032 KB
testcase_14 AC 129 ms
53,904 KB
testcase_15 AC 128 ms
54,168 KB
testcase_16 AC 132 ms
54,172 KB
testcase_17 AC 128 ms
54,388 KB
testcase_18 AC 128 ms
54,016 KB
testcase_19 AC 129 ms
54,292 KB
testcase_20 AC 115 ms
53,144 KB
testcase_21 AC 135 ms
54,304 KB
testcase_22 AC 128 ms
54,196 KB
testcase_23 AC 128 ms
54,336 KB
testcase_24 AC 129 ms
54,276 KB
testcase_25 AC 129 ms
54,400 KB
testcase_26 AC 129 ms
54,240 KB
testcase_27 AC 129 ms
54,032 KB
testcase_28 AC 131 ms
54,148 KB
testcase_29 AC 132 ms
54,008 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.math.BigInteger;
import java.util.Scanner;
public class main{
	static Scanner sc=new Scanner(System.in);
	public static void main(String args[]){
		int n=sc.nextInt();
		long[][] A={
				{1,3},
				{1,1}
		};
		A=MtPow(n,A);
		long a=A[0][0];
		if(n%2==0){
			System.out.print((2*a-1)%1000);
		}else{
			System.out.print((2*a)%1000);
		}
	}

//int matrix^matrix(becareful about the size)
public static long[][] MtPrd(long[][] A,long[][] B){
	long[][] C=new long[A.length][B[0].length];
	for(int i=0;i<A.length;i++){
		for(int j=0;j<B[0].length;j++){
			for(int k=0;k<B[0].length;k++){
				C[i][j]+=A[i][k]*B[k][j];
				C[i][j]%=1000;
			}
		}
	}
	return C;
}
//A+B
public static long[][] MtSum(long[][] A,long[][] B){
	long[][] C=new long[A[0].length][A.length];
	for(int i=0;i<A.length;i++){
		for(int j=0;j<A[0].length;j++){
			C[i][j]=A[i][j]+B[i][j];
		}
	}
	return C;
}
//convert to binary
public static BigInteger bi(int n){
	BigInteger b=new BigInteger("0");
	BigInteger digit=new BigInteger("10");
	for(int i=0;n!=0;i++){
		//System.out.println("n="+n+"\nb="+b);
		if(n%2==0){
			n/=2;
		}else{
			n-=1;
			n/=2;
			b=b.add(digit.pow(i));
		}
	}
	return b;
}

//R=A^n
public static long[][] MtPow(int n,long[][] A){
	BigInteger b=new BigInteger("0");
	b=bi(n);
	long[][] B=new long[A.length][A[0].length];
	for(int i=0;i<A.length;i++){
		B[i][i]=1;
	}
	while(b.compareTo(BigInteger.valueOf(1))>=0){
		if((b.remainder(BigInteger.valueOf(10)).compareTo(BigInteger.valueOf(1)))==0){
			B=MtPrd(A,B);
			b=b.subtract(BigInteger.valueOf(-1));
			b=b.divide(BigInteger.valueOf(10));
		}else if((b.remainder(BigInteger.valueOf(10)).compareTo(BigInteger.valueOf(1)))!=0){
			b=b.divide(BigInteger.valueOf(10));
		}
		A=MtPrd(A,A);
	}
	return B;
}
}
0