結果

問題 No.2181 LRM Question 2
ユーザー 37zigen37zigen
提出日時 2022-10-14 10:02:18
言語 Java21
(openjdk 21)
結果
WA  
実行時間 -
コード長 4,944 bytes
コンパイル時間 2,736 ms
コンパイル使用メモリ 81,140 KB
実行使用メモリ 58,172 KB
最終ジャッジ日時 2024-06-26 12:31:06
合計ジャッジ時間 14,834 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 56 ms
36,624 KB
testcase_01 AC 53 ms
36,876 KB
testcase_02 AC 1,042 ms
43,188 KB
testcase_03 AC 54 ms
36,832 KB
testcase_04 AC 56 ms
36,776 KB
testcase_05 AC 56 ms
37,004 KB
testcase_06 AC 55 ms
36,664 KB
testcase_07 AC 55 ms
36,624 KB
testcase_08 AC 1,523 ms
42,876 KB
testcase_09 WA -
testcase_10 AC 1,965 ms
42,944 KB
testcase_11 AC 1,837 ms
42,784 KB
testcase_12 AC 1,958 ms
42,768 KB
testcase_13 AC 59 ms
36,932 KB
testcase_14 AC 217 ms
53,940 KB
testcase_15 AC 109 ms
39,200 KB
testcase_16 AC 213 ms
51,112 KB
testcase_17 AC 117 ms
39,100 KB
testcase_18 AC 168 ms
39,092 KB
testcase_19 AC 64 ms
36,712 KB
testcase_20 AC 172 ms
42,812 KB
testcase_21 AC 287 ms
42,412 KB
testcase_22 AC 147 ms
42,232 KB
testcase_23 WA -
testcase_24 WA -
testcase_25 WA -
権限があれば一括ダウンロードができます

ソースコード

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_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();
	}
	
	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);
		long[] v = new long[primes.size()];
		for (int i = 0; i < primes.size(); ++i) {
			int p = primes.get(i).intValue();
			int pe = (int) pow_mod(primes.get(i), indexes.get(i), 10 * M);
			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 (int j = fac.length - 1; j >= 1; --j) {
				int nj = j;
				do {
					nj /= p;
					fac[j] = fac[j] * fac[nj] % pe;
					ifac[j] = ifac[j] * ifac[nj] % pe;
				} while (nj != 0);
			}
			for (long n = L; n <= R; ++n) {
				long comb = 1;
				{
					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;
						a /= pe;
						b /= pe;
					} while (a != 0);
				}
				long e = 0;
				long f = 0;
				{
					long a = 2 * n;
					long b = n;
					while (a > 0) {
						f += a / pe - b / pe * 2;
						e += a / p - b / p * 2;
						a /= p;
						b /= p;
					}
				}
				e = Math.min(e, indexes.get(i));
				comb = comb * pow_mod(p, e, pe) % pe;
				comb = comb * pow_mod(fac[fac.length - 1], f, pe) % pe;
				v[i] = (v[i] + comb) % pe;
			}
		}
		for (long i = 0; i < M; ++i) {
			boolean ok = true;
			for (int j = 0; j < primes.size(); ++j) {
				ok &= v[j] == i % pow_mod(primes.get(j), indexes.get(j), 10 * M);
			}
			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();
	}
}
0