#806693 (Java21) No.2181 LRM Question 2

• 問題: No.2181 LRM Question 2
• ユーザー: 37zigen
• 提出日時: 2022-10-14 11:55:19
• 言語: Java21 (openjdk 21)
• 結果: AC
• 実行時間: 1,992 ms / 2,000 ms
• コード長: 5,404 bytes
• コンパイル時間: 2,620 ms
• コンパイル使用メモリ: 81,788 KB
• 実行使用メモリ: 54,112 KB
• 最終ジャッジ日時: 2024-06-26 12:33:06
• 合計ジャッジ時間: 14,637 ms
• ジャッジサーバーID （参考情報）: judge2 / judge4

入力	結果	実行時間; 実行使用メモリ
testcase_00	AC	54 ms; 37,188 KB
testcase_01	AC	54 ms; 36,660 KB
testcase_02	AC	1,245 ms; 42,568 KB
testcase_03	AC	54 ms; 36,828 KB
testcase_04	AC	55 ms; 36,992 KB
testcase_05	AC	55 ms; 37,188 KB
testcase_06	AC	55 ms; 36,860 KB
testcase_07	AC	53 ms; 37,180 KB
testcase_08	AC	1,479 ms; 42,312 KB
testcase_09	AC	485 ms; 42,660 KB
testcase_10	AC	1,943 ms; 42,276 KB
testcase_11	AC	1,989 ms; 42,312 KB
testcase_12	AC	1,992 ms; 42,412 KB
testcase_13	AC	56 ms; 36,760 KB
testcase_14	AC	161 ms; 54,112 KB
testcase_15	AC	91 ms; 39,312 KB
testcase_16	AC	156 ms; 51,172 KB
testcase_17	AC	118 ms; 40,084 KB
testcase_18	AC	123 ms; 38,564 KB
testcase_19	AC	62 ms; 37,172 KB
testcase_20	AC	124 ms; 42,484 KB
testcase_21	AC	325 ms; 42,556 KB
testcase_22	AC	125 ms; 39,124 KB
testcase_23	AC	54 ms; 37,044 KB
testcase_24	AC	55 ms; 36,596 KB
testcase_25	AC	54 ms; 37,044 KB

ソースコード

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);
		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) % 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(primes.get(j), indexes.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();
	}
}