結果

問題 No.2181 LRM Question 2
ユーザー 37zigen
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

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++];
else
return -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();
}
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0