結果
問題 | No.109 N! mod M |
ユーザー | ぴろず |
提出日時 | 2015-03-06 17:04:57 |
言語 | Java19 (openjdk 21) |
結果 |
AC
|
実行時間 | 274 ms / 5,000 ms |
コード長 | 1,937 bytes |
コンパイル時間 | 2,195 ms |
コンパイル使用メモリ | 80,904 KB |
実行使用メモリ | 56,836 KB |
最終ジャッジ日時 | 2023-09-04 05:23:50 |
合計ジャッジ時間 | 4,638 ms |
ジャッジサーバーID (参考情報) |
judge14 / judge12 |
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 149 ms
56,096 KB |
testcase_01 | AC | 246 ms
56,000 KB |
testcase_02 | AC | 270 ms
56,200 KB |
testcase_03 | AC | 155 ms
55,988 KB |
testcase_04 | AC | 199 ms
56,720 KB |
testcase_05 | AC | 274 ms
56,836 KB |
testcase_06 | AC | 184 ms
56,656 KB |
testcase_07 | AC | 155 ms
55,540 KB |
testcase_08 | AC | 155 ms
55,900 KB |
ソースコード
package no109a; import java.util.ArrayList; import java.util.Arrays; import java.util.Scanner; public class Main { public static void main(String[] args) { ArrayList<Integer> primes = Sieve.primeList((int) Math.sqrt(1_000_000_000) + 2); Scanner sc = new Scanner(System.in); int t = sc.nextInt(); for(int tt=0;tt<t;tt++) { int n = sc.nextInt(); int m = sc.nextInt(); long ans = 1; if (m <= n) { ans = 0; }else if (m <= 200000) { for(int i=1;i<=n;i++) { ans = ans * i % m; } }else{ if (Sieve.primeFactorL(primes, m).size() >= 2) { ans = 0; }else{ long div = 1; for(int i=n+1;i<=m-1;i++) { div = div * i % m; } ans = (m - 1) * modInv(div, m) % m; } } System.out.println(ans % m); } } public static long modpow(long x,long n,long mod) { long res = 1; while(n > 0) { if ((n & 1) > 0) { res = (res * x) % mod; } x = (x * x) % mod; n/=2; } return res; } public static long modInv(long x,long modP) { return modpow(x, modP-2, modP); } } class Sieve { public static boolean[] isPrimeArray(int max) { boolean[] isPrime = new boolean[max+1]; Arrays.fill(isPrime, true); isPrime[0] = isPrime[1] = false; for(int i=2;i*i<=max;i++) { if (isPrime[i]) { int j = i * 2; while(j<=max) { isPrime[j] = false; j += i; } } } return isPrime; } public static ArrayList<Integer> primeList(int max) { boolean[] isPrime = isPrimeArray(max); ArrayList<Integer> primeList = new ArrayList<Integer>(); for(int i=2;i<=max;i++) { if (isPrime[i]) { primeList.add(i); } } return primeList; } public static ArrayList<Long> primeFactorL(ArrayList<Integer> primeList,long num) { ArrayList<Long> ret = new ArrayList<Long>(); for(int p:primeList) { while(num % p == 0) { num /= p; ret.add((long) p); } } if (num > 1) { ret.add(num); } return ret; } }