結果

問題 No.3038 フィボナッチ数列の周期
ユーザー tanzakutanzaku
提出日時 2018-04-01 23:46:12
言語 Java21
(openjdk 21)
結果
TLE  
実行時間 -
コード長 4,163 bytes
コンパイル時間 2,294 ms
コンパイル使用メモリ 81,632 KB
実行使用メモリ 42,324 KB
最終ジャッジ日時 2024-06-26 06:14:18
合計ジャッジ時間 9,331 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 132 ms
41,824 KB
testcase_01 AC 130 ms
41,544 KB
testcase_02 AC 136 ms
41,520 KB
testcase_03 AC 133 ms
41,840 KB
testcase_04 AC 130 ms
41,704 KB
testcase_05 AC 120 ms
40,244 KB
testcase_06 AC 128 ms
41,908 KB
testcase_07 AC 151 ms
42,324 KB
testcase_08 AC 133 ms
41,524 KB
testcase_09 AC 148 ms
41,984 KB
testcase_10 AC 151 ms
42,204 KB
testcase_11 AC 146 ms
42,092 KB
testcase_12 AC 150 ms
42,196 KB
testcase_13 AC 150 ms
42,164 KB
testcase_14 AC 146 ms
41,944 KB
testcase_15 AC 150 ms
41,924 KB
testcase_16 TLE -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.PrintWriter;
import java.math.BigInteger;
import java.util.Arrays;
import java.util.Scanner;

public class Main {
	void solveTestcase(final Scanner in, final PrintWriter out) {
		final int mod = (int)(1e9)+7;
		int n = in.nextInt();

		BigInteger ans = BigInteger.ONE;
		for (int i = 0; i < n; i++) {
			int p = in.nextInt();
			int k = in.nextInt();
			BigInteger val = BigInteger.valueOf(p).pow(k - 1);
//			dump(i, period, fibonacciPeriod(p));
			val = val.multiply(BigInteger.valueOf(fibonacciPeriod(p)));
			ans = ans.divide(ans.gcd(val)).multiply(val);
		}
//		chineseReminder(A, B, M);
		out.println(ans.mod(BigInteger.valueOf(mod)));
	}
	static long gcd(long n, long r) { return r == 0 ? n : gcd(r, n%r); }
	static long lcm(long n, long r) { return n / gcd(n, r) * r; }
	
	void solve() {
		try (final PrintWriter out = new PrintWriter(System.out)) {
			try (final Scanner in = new Scanner(System.in)) {
//				int t = in.nextInt();
				int t = 1;
				while (t-- > 0) {
					solveTestcase(in, out);
				}
			}
		}
	}

	public static void main(String[] args) {
		new Main().solve();
	}
	
	static long fibonacciPeriod(int mod) {
		if (mod == 2) {
			return 3;
		}
		if (mod == 5) {
			return 20;
		}
		long ans = Long.MAX_VALUE;
		if (mod % 10 == 1 || mod % 10 == 9) {
			final int d = mod - 1;
			for (int i = 1; i*i <= d && i < ans; i++) {
				if (d % i == 0) {
					if (periodic(d / i, mod)) {
						ans = Math.min(ans, d / i);
					}
					if (periodic(i, mod)) {
						ans = Math.min(ans, i);
					}
				}
			}
		}
		if (mod % 10 == 3 || mod % 10 == 7) {
			final int d = 2 * (mod + 1);
			for (int i = 1; i*i <= d && i < ans; i++) {
				if (d % i == 0) {
					if (i % 2 == 1 && periodic(d / i, mod)) {
//					if (periodic(d / i, mod)) {
						ans = Math.min(ans, d / i);
					}
					if (d / i % 2 == 1 && periodic(i, mod)) {
//					if (periodic(i, mod)) {
						ans = Math.min(ans, i);
					}
				}
			}
		}
		return ans;
	}
	
	static boolean periodic(int p, int mod) {
		return fib(p, mod) == 0 && fib(p+1, mod) == 1;
	}
	
	// a [n,v] * b [v,m] => c[n,m]
	static long[][] mulmat(long[][] a, long[][] b, int mod) {
		final long BIG = (2L * mod) * (2L * mod);
		
		assert(a[0].length == b.length);
		
		final int n = a.length;
		final int v = b.length;
		final int m = b[0].length;
		
		long[][] res = new long[n][m];
		for(int i = 0; i < n; i++)
			for(int k = 0; k < v; k++) {
				final long aa = a[i][k];
				for(int j = 0; j < m; j++) {
					res[i][j] += aa * b[k][j];
					if(res[i][j] >= BIG) res[i][j] -= BIG;
				}
			}
		for(int i = 0; i < n; i++)
			for(int j = 0; j < m; j++)
				res[i][j] %= mod;
		
		return res;
	}
	
	static long[][] powmat(long r, int mod, long[][] mat) {
		final int n = mat.length;
		long[][] x = new long[n][n];
		for(int i = 0; i < n; i++) {
			x[i][i] = 1;
		}
		
		for(;r > 0; r >>>= 1) {
			if((r&1) == 1) {
				x = mulmat(x, mat, mod);
			}
			mat = mulmat(mat, mat, mod);
		}

		return x;
	}
	
	static long fib(long n, int mod) {
		long[][] mat = new long[][]{
				new long[]{1, 1,},
				new long[]{1, 0,},
		};
		return powmat(n, mod, mat)[1][0];
	}
	
	// A[i]*x == B[i] mod M[i]
	static int[] chineseReminder(int[] A, int[] B, int[] M) {
		long x = 0;
		int m = 1;
		for(int i = 0; i < A.length; i++) {
			long a = A[i] * m, b = B[i] - A[i] * x, d = gcd(M[i], a);
			if(b % d != 0) return new int[] { 0, -1 };
			int t = (int)(b / d * modInverse(a / d, M[i] / d) % (M[i] / d));
			x += (long)m * t;
			m *= M[i] / d;
		}
		return new int[] { (int)((x % m + m) % m), m };
	}

	// n^-1 mod m を求める
	// 存在しなかったら-1を返す
	static long modInverse(final long n, final long m) {
		final long[] res = extGcd(n, m);
		return res[2] != 1 ? -1 : (m + res[0]) % m;
	}

	// ax+by=c(=gcd(a,b))
	// なるx,yを求める
	// return [x,y,c]
	static long[] extGcd(final long a, final long b) {
		if (b == 0) {
			return new long[] { 1, 0, a };
		}
		final long[] res = extGcd(b, a % b);
		long y = res[0];
		final long x = res[1];
		y -= (a / b) * x;
		res[0] = x;
		res[1] = y;
		return res;
	}

	static void dump(Object...objects) { System.err.println(Arrays.deepToString(objects)); }
}
0