結果

問題 No.344 ある無理数の累乗
ユーザー 37zigen
提出日時 2016-02-13 11:53:00
言語 Java
(openjdk 23)
結果
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
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

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;
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0