結果
| 問題 | No.8038 フィボナッチ数列の周期 |
| ユーザー |
 Grenache
|
| 提出日時 | 2018-04-02 17:45:59 |
| 言語 | Java (openjdk 23) |
| 結果 |
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 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 25 |
ソースコード
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;}@Overridepublic Iterator<Integer> iterator() {return new PrimeIterator();}private class PrimeIterator implements Iterator<Integer> {int index;PrimeIterator() {index = -1;}@Overridepublic boolean hasNext() {if (index == -1) {return n >= 2;} else {return 2 * (index + 1) + 1 <= n;}}@Overridepublic 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);}}}