結果

問題 No.2181 LRM Question 2
ユーザー 37zigen37zigen
提出日時 2022-10-18 19:30:40
言語 Java21
(openjdk 21)
結果
AC  
実行時間 1,825 ms / 2,000 ms
コード長 5,683 bytes
コンパイル時間 2,428 ms
コンパイル使用メモリ 83,144 KB
実行使用メモリ 53,956 KB
最終ジャッジ日時 2024-06-29 02:28:04
合計ジャッジ時間 13,788 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 51 ms
36,412 KB
testcase_01 AC 50 ms
36,792 KB
testcase_02 AC 1,112 ms
42,492 KB
testcase_03 AC 51 ms
36,720 KB
testcase_04 AC 51 ms
36,844 KB
testcase_05 AC 52 ms
36,716 KB
testcase_06 AC 52 ms
37,116 KB
testcase_07 AC 52 ms
36,864 KB
testcase_08 AC 1,315 ms
42,068 KB
testcase_09 AC 470 ms
42,684 KB
testcase_10 AC 1,777 ms
42,008 KB
testcase_11 AC 1,825 ms
41,928 KB
testcase_12 AC 1,817 ms
42,100 KB
testcase_13 AC 53 ms
37,108 KB
testcase_14 AC 146 ms
53,956 KB
testcase_15 AC 76 ms
39,248 KB
testcase_16 AC 150 ms
50,916 KB
testcase_17 AC 112 ms
39,992 KB
testcase_18 AC 89 ms
39,064 KB
testcase_19 AC 60 ms
36,980 KB
testcase_20 AC 105 ms
42,352 KB
testcase_21 AC 308 ms
42,544 KB
testcase_22 AC 89 ms
38,896 KB
testcase_23 AC 51 ms
36,924 KB
testcase_24 AC 51 ms
37,068 KB
testcase_25 AC 50 ms
36,384 KB
権限があれば一括ダウンロードができます

ソースコード

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();
		if (!(2 <= L && L <= R && R <= 1e18)) throw new AssertionError();
		if (!(R-L <= 1e5)) throw new AssertionError();
		if (!(1 <= M && M <= 1e6)) throw new AssertionError();
		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();
	}
}
0