結果

問題 No.3038 フィボナッチ数列の周期
ユーザー GrenacheGrenache
提出日時 2018-04-02 17:45:59
言語 Java21
(openjdk 21)
結果
AC  
実行時間 387 ms / 3,000 ms
コード長 5,629 bytes
コンパイル時間 4,576 ms
コンパイル使用メモリ 82,276 KB
実行使用メモリ 59,032 KB
最終ジャッジ日時 2024-06-26 06:41:35
合計ジャッジ時間 11,536 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge1
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 149 ms
54,128 KB
testcase_01 AC 149 ms
54,068 KB
testcase_02 AC 154 ms
54,120 KB
testcase_03 AC 149 ms
53,960 KB
testcase_04 AC 147 ms
54,132 KB
testcase_05 AC 147 ms
53,976 KB
testcase_06 AC 143 ms
53,776 KB
testcase_07 AC 157 ms
54,696 KB
testcase_08 AC 160 ms
53,992 KB
testcase_09 AC 153 ms
54,108 KB
testcase_10 AC 162 ms
54,116 KB
testcase_11 AC 152 ms
53,824 KB
testcase_12 AC 154 ms
54,080 KB
testcase_13 AC 157 ms
53,916 KB
testcase_14 AC 160 ms
54,100 KB
testcase_15 AC 158 ms
54,064 KB
testcase_16 AC 387 ms
58,828 KB
testcase_17 AC 387 ms
58,116 KB
testcase_18 AC 368 ms
58,172 KB
testcase_19 AC 364 ms
58,300 KB
testcase_20 AC 371 ms
58,128 KB
testcase_21 AC 377 ms
58,392 KB
testcase_22 AC 385 ms
58,268 KB
testcase_23 AC 374 ms
59,032 KB
testcase_24 AC 378 ms
58,676 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

import java.io.*;
import java.util.*;
import java.util.Map.*;


public class Main_yukicoder3038 {

	private static Scanner sc;
	private static Printer pr;

	private static void solve() {
		int n = sc.nextInt();

		int[] p = new int[n];
		int[] k = new int[n];
		for (int i = 0; i < n; i++) {
			p[i] = sc.nextInt();
			k[i] = sc.nextInt();
		}

		Prime prime = new Prime(100_000);

		Map<Long, Integer> lcm = new HashMap<>();
		for (int i = 0; i < n; i++) {
			Map<Long, Integer> pf = prime.primeFactorize(a(p[i]));
			if (k[i] > 1) {
				if (pf.containsKey((long)p[i])) {
					pf.put((long)p[i], pf.get((long)p[i]) + k[i] - 1);
				} else {
					pf.put((long)p[i], k[i] - 1);
				}
			}

			for (Entry<Long, Integer> e : pf.entrySet()) {
				long key = e.getKey();
				int value = e.getValue();

				if (lcm.containsKey(key)) {
					lcm.put(key, Math.max(lcm.get(key), value));
				} else {
					lcm.put(key, value);
				}
			}
		}

		long ans = 1;
		for (Entry<Long, Integer> e : lcm.entrySet()) {
			ans *= modPow(e.getKey(), e.getValue(), MOD);
			ans %= MOD;
		}

		pr.println(ans);
	}

	static final int MOD = 1_000_000_007;

	private static long a(int n) {
		switch (n) {
			case 2:
				return 3;
			case 3:
				return 8;
			case 5:
				return 20;
			default:
				int mod = n % 5;
				if (mod == 1 || mod == 4) {
					int ret = n - 1;
					int min = n - 1;
					for (int i = 2; (long)i * i <= ret; i++) {
						if (ret % i == 0) {
							if (fibonacciNumber(i, n) == 0 && fibonacciNumber(i + 1, n) == 1) {
								return i;
							}
							if (fibonacciNumber(ret / i, n) == 0 && fibonacciNumber(ret / i + 1, n) == 1) {
								min = Math.min(min, ret / i);
							}
						}
					}

					return min;
				} else if (mod == 2 || mod == 3) {
					int ret = 2 * n + 2;
					int min = 2 * n + 2;
					for (int i = 2; (long)i * i <= ret; i++) {
						if (ret % i == 0) {
							if (fibonacciNumber(i, n) == 0 && fibonacciNumber(i + 1, n) == 1) {
								return i;
							}
							if (fibonacciNumber(ret / i, n) == 0 && fibonacciNumber(ret / i + 1, n) == 1) {
								min = Math.min(min, ret / i);
							}
						}
					}

					return min;
				} else {
					pr.println("err");
					return -1;
				}
		}
	}

	private static long fibonacciNumber(long n, int MOD) {
		// f(0)=0, f(1)=1, f(2)=1,...

		long[] a = {1, 1, 1, 0};
		long[] x = {1, 0};
		while(n > 0) {
			if (n % 2 != 0) {
				long tmp0 = (x[0] * a[0] + x[1] * a[1]) % MOD;
				long tmp1 = (x[0] * a[2] + x[1] * a[3]) % MOD;
				x[0] = tmp0;
				x[1] = tmp1;
			}
			long tmp0 = (a[0] * a[0] + a[1] * a[2]) % MOD;
			long tmp1 = a[1] * (a[0] + a[3]) % MOD;
			long tmp2 = a[2] * (a[0] + a[3]) % MOD;
			long tmp3 = (a[3] * a[3] + a[1] * a[2]) % MOD;
			a[0] = tmp0;
			a[1] = tmp1;
			a[2] = tmp2;
			a[3] = tmp3;
			n /= 2;
		}

		return x[1];
	}

	static class Prime implements Iterable<Integer> {
		private int n;
		private BitSet p;

		Prime(int n) {
			this.n = n;

			p = new BitSet(n / 2);
			int m = (int)Math.sqrt(n);

//			for (int i = 1; i <= m; i++) {
			for (int bi = p.nextClearBit(0); 2 * (bi + 1) + 1 <= m; bi = p.nextClearBit(bi + 1)) {
				long i = bi + 1;
//				if (p.get(i - 1)) {
//					continue;
//				}

				for (long j = 2 * i * (i + 1); 2 * j + 1 <= n; j += 2 * i + 1) {
					p.set((int)(j - 1));
				}
			}
		}

		boolean isPrime(int n) {
			if (n == 2) {
				return true;
			}

			if (n == 1 || (n & 0x1) == 0) {
				return false;
			}

			return !p.get(n / 2 - 1);
		}

		List<Integer> getPrimeList() {
			List<Integer> ret = new ArrayList<>();
			for (int p : this) {
				ret.add(p);
			}

			return ret;
		}

		Map<Long, Integer> primeFactorize(long x) {
			Map<Long, Integer> hm = new TreeMap<>();
			long n = x;
			for (int p : this) {
				if ((long)p * p > n) {
					break;
				}
				int cnt = 0;
				while (n % p == 0) {
					cnt++;
					n /= p;
				}
				if (cnt > 0) {
					hm.put((long)p, cnt);
				}
			}
			if (n != 1) {
				hm.put(n, 1);
			}

			return hm;
		}

		@Override
		public Iterator<Integer> iterator() {
			return new PrimeIterator();
		}

		private class PrimeIterator implements Iterator<Integer> {
			int index;

			PrimeIterator() {
				index = -1;
			}

			@Override
			public boolean hasNext() {
				if (index == -1) {
					return n >= 2;
				} else {
					return 2 * (index + 1) + 1 <= n;
				}
			}

			@Override
			public Integer next() {
				if (index == -1) {
					if (n >= 2) {
						index = p.nextClearBit(0);
						return 2;
					} else {
						throw new NoSuchElementException();
					}
				} else {
					int ret = 2 * (index + 1) + 1;

					if (ret <= n) {
						index = p.nextClearBit(index + 1);

						return ret;
					} else {
						throw new NoSuchElementException();
					}
				}
			}
		}

		static boolean isPrime(long n) {
			if (n == 2) {
				return true;
			}

			if (n == 1 || (n & 0x1) == 0) {
				return false;
			}

			for (long i = 3; i * i <= n; i += 2) {
				if (n % i == 0) {
					return false;
				}
			}

			return true;
		}
	}

	static long modPow(long a, long n, int MOD) {
		long loop = n;
		long ret = 1;
		long x = a % MOD;
		while (loop > 0) {
			if (loop % 2 == 1) {
				ret = ret * x % MOD;
			}
			x = x * x % MOD;
			loop /= 2;
		}

		return ret;
	}

	// ---------------------------------------------------
	public static void main(String[] args) {
		sc = new Scanner(INPUT == null ? System.in : new ByteArrayInputStream(INPUT.getBytes()));
		pr = new Printer(System.out);

		solve();

//		pr.close();
		pr.flush();
//		sc.close();
	}

	static String INPUT = null;

	private static class Printer extends PrintWriter {
		Printer(OutputStream out) {
			super(out);
		}
	}
}
0