結果
問題 | No.2181 LRM Question 2 |
ユーザー |
|
提出日時 | 2022-10-14 20:43:38 |
言語 | Java (openjdk 23) |
結果 |
AC
|
実行時間 | 1,883 ms / 2,000 ms |
コード長 | 5,509 bytes |
コンパイル時間 | 2,732 ms |
コンパイル使用メモリ | 82,000 KB |
実行使用メモリ | 54,048 KB |
最終ジャッジ日時 | 2024-06-26 12:45:24 |
合計ジャッジ時間 | 14,119 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 23 |
ソースコード
import java.io.IOException;import java.io.InputStream;import java.io.PrintWriter;import java.util.ArrayList;import java.util.Arrays;import java.util.List;import java.util.NoSuchElementException;public class Main implements Runnable {public static void main(String[] args) {// new Thread(null, new Main(), "", Runtime.getRuntime().maxMemory()).start();new Main().run();}long pow(long a, long n) {if (n == 0) return 1;return pow(a*a,n/2)*(n%2==1?a:1);}long pow_mod(long a, long n, long mod) {a %= mod;if (n == 0) return 1;return pow_mod(a * a % mod, n / 2, mod) * (n % 2 == 1 ? a : 1) % mod;}long inv(long a, long mod, long ord) {return pow_mod(a, ord-1, mod);}long gcd(long a, long b) {if (a == 0) return b;else return gcd(b % a, a);}public void run() {FastScanner sc = new FastScanner();PrintWriter pw=new PrintWriter(System.out);long L = sc.nextLong();long R = sc.nextLong();long M = sc.nextLong();pw.println(solve(L, R, M));pw.close();}long[][] rec = new long[100][100];void init() {for (int i = 0; i < rec.length; ++i) {for (int j = 0; j < rec[i].length; ++j) {rec[i][j] = -1;}}}long c(long n, long k, long mod) {if (k<0||n-k<0) return 0;if (k == 0 || k == n) return 1;if (rec[(int)n][(int)k] != -1) return rec[(int)n][(int)k];return rec[(int)n][(int)k] = (c(n-1, k, mod) + c(n-1, k-1, mod))%mod;}long exact(long L, long R, long M) {init();long ret = 0;for (long n = L; n <= R; ++n) {ret = (ret + c(2 * n, n, M))% M;}ret = (ret % M + M) % M;return ret;}long coprime(long a, long m) {while (gcd(a, m) != 1) {a /= gcd(a, m);}return a;}List<ArrayList<? extends Number>> factor(long n) {ArrayList<Long> primes = new ArrayList<>();ArrayList<Integer> indexes = new ArrayList<>();for (long i = 2; i * i <= n; ++i) {int e = 0;while (n % i == 0) {n /= i;++e;}if (e != 0) {primes.add(i);indexes.add(e);}}if (n != 1) {primes.add(n);indexes.add(1);}return List.of(primes, indexes);}long solve(long L, long R, long M) {if (M == 1) return 0;var factor = factor(M);ArrayList<Long> primes = (ArrayList<Long>) factor.get(0);ArrayList<Integer> indexes = (ArrayList<Integer>) factor.get(1);ArrayList<Long> pes = new ArrayList<>();for (int i = 0; i < primes.size(); ++i) pes.add(pow(primes.get(i), indexes.get(i)));long[] v = new long[primes.size()];for (int i = 0; i < primes.size(); ++i) {int p = primes.get(i).intValue();int pe = (int) pow(primes.get(i), indexes.get(i));long[] fac = new long[pe + 1];long[] ifac = new long[fac.length];Arrays.fill(fac, 1);Arrays.fill(ifac, 1);for (int j = 1; j < fac.length; ++j) fac[j] = (j % p == 0 ? 1 : j ) * fac[j - 1] % pe;ifac[fac.length - 1] = fac[fac.length - 1];for (int j = ifac.length - 1; j >= 1; --j) ifac[j - 1] = (j % p == 0 ? 1 : j ) * ifac[j] % pe;for (long n = L; n <= R; ++n) {long comb = 1;long e = 0;long f = 0;{long a = 2 * n;long b = n;do {comb = comb * fac[(int) (a%pe)] % pe * ifac[(int) (b%pe)] % pe * ifac[(int) (b%pe)] % pe;f += a / pe - b / pe * 2;e += a / p - b / p * 2;a /= p;b /= p;} while (a != 0);}e = Math.min(e, indexes.get(i));comb = comb * pow_mod(p, e, pe);comb = comb * (f % 2 == 1 ? fac[fac.length - 1] : 1);v[i] = (v[i] + comb) % pe;}}for (long i = 0; i < M; ++i) {boolean ok = true;for (int j = 0; j < primes.size() && ok; ++j) {ok &= v[j] == i % pes.get(j);}if (ok) {long ans = i - 2 * (R - L + 1);ans = (ans % M + M) % M;return ans;}}throw new AssertionError();}void tr(Object... objects) {System.err.println(Arrays.deepToString(objects));}}class FastScanner {private final InputStream in = System.in;private final byte[] buffer = new byte[1024];private int ptr = 0;private int buflen = 0;private boolean hasNextByte() {if (ptr < buflen) {return true;} else {ptr = 0;try {buflen = in.read(buffer);} catch (IOException e) {e.printStackTrace();}if (buflen <= 0) {return false;}}return true;}private int readByte() {if (hasNextByte())return buffer[ptr++];elsereturn -1;}private static boolean isPrintableChar(int c) {return 33 <= c && c <= 126;}private void skipUnprintable() {while (hasNextByte() && !isPrintableChar(buffer[ptr]))ptr++;}public boolean hasNext() {skipUnprintable();return hasNextByte();}public String next() {if (!hasNext())throw new NoSuchElementException();StringBuilder sb = new StringBuilder();int b = readByte();while (isPrintableChar(b)) {sb.appendCodePoint(b);b = readByte();}return sb.toString();}public long nextLong() {if (!hasNext())throw new NoSuchElementException();long n = 0;boolean minus = false;int b = readByte();if (b == '-') {minus = true;b = readByte();}if (b < '0' || '9' < b) {throw new NumberFormatException();}while (true) {if ('0' <= b && b <= '9') {n *= 10;n += b - '0';} else if (b == -1 || !isPrintableChar(b)) {return minus ? -n : n;} else {throw new NumberFormatException();}b = readByte();}}public int nextInt() {return (int) nextLong();}}