結果

問題 No.109 N! mod M
ユーザー 37zigen37zigen
提出日時 2016-05-03 16:19:30
言語 Java21
(openjdk 21)
結果
AC  
実行時間 307 ms / 5,000 ms
コード長 3,137 bytes
コンパイル時間 2,325 ms
コンパイル使用メモリ 80,920 KB
実行使用メモリ 56,316 KB
最終ジャッジ日時 2023-09-04 05:33:43
合計ジャッジ時間 5,274 ms
ジャッジサーバーID
（参考情報） 		judge15 / judge13
このコードへのチャレンジ（β）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 195 ms
55,880 KB
testcase_01 AC 286 ms
56,284 KB
testcase_02 AC 302 ms
55,984 KB
testcase_03 AC 201 ms
55,856 KB
testcase_04 AC 206 ms
56,304 KB
testcase_05 AC 307 ms
56,204 KB
testcase_06 AC 200 ms
56,316 KB
testcase_07 AC 172 ms
53,864 KB
testcase_08 AC 199 ms
56,108 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

package yukicoder;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Scanner;

public class Main{
	public static void main(String[] args)throws Exception{
		new Main().solve();
	}
	ArrayList<Integer> primes=new Prime().primeList((int)Math.sqrt(1000000000));
	void solve(){
		Scanner sc=new Scanner(System.in);
		int t=sc.nextInt();
		for(int i=0;i<t;i++){
			long n=sc.nextLong();
			long m=sc.nextLong();
			ArrayList<Factor> list=new Prime().primeFactorF(primes, m);
//			for(int j=0;j<list.size();j++){
//				Factor f=list.get(j);
//				System.out.println(f.base+" "+f.exp);
//			}	
			System.out.println(factorial_mod(n, m));
		}

	}
	void tr(Object...o){System.out.println(Arrays.deepToString(o));}
	long factorial_mod(long n,long m){
		if(n>=m){
			return 0;
		}else if(n<=2*Math.pow(10,5)){
			if(n==0)return 1%m;
			long ans=1;
			for(int i=1;i<=n;i++){
				ans=ans*i%m;
			}
			return ans;
		}else if(new Prime().primeFactorF(primes, m).size()>=2)return 0;
		else{
			long ans=m-1;
			long a=1;
			for(long i=m-1;i>=n+1;i--){
				a*=i;
				a%=m;
			}
			long aa=inverse_element(a, m);
			while(aa<0)aa+=m;
			ans*=aa;
			ans%=m;
			return ans;
		}
	}

	class Prime{
		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]){
					for(int j=2;j*i<=max;j++){
						isPrime[j*i]=false;
					}
				}
			}
			return isPrime;
		}
		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;
		}
		ArrayList<Factor> primeFactorF(ArrayList<Integer> primeList,long num){
			ArrayList<Factor> ret=new ArrayList<Factor>();
			for(int p:primeList){
				int exp=0;
				while(num%p==0){
					num/=p;
					exp++;
				}
				if(exp>0)ret.add(new Factor(p,exp));
			}
			if(num>1)ret.add(new Factor((int)num,1));
			return ret;
		}
	}
	class Factor{
		int base,exp;
		Factor(int base,int exp){
			this.base=base;
			this.exp=exp;
		}
	}
	/**
	 * ax=1 mod p
	 * となる逆元x=a^(-1)を求める。
	 * pが素数でないときは逆元は存在しない(正しくない値を返す)。
	 * 拡張ユークリッドの控除法を用いた。
	 */
	long inverse_element(long a,long p){
		return extended_Euclid(1, 0, a, 0, 1, p)[0];
	}
	/**
	 *ax=1 mod p となるxを求める。
	 *ax+py=1を満たす、(x,y)を求めればよい。
	 *拡張ユークリッドの控除法を用いる。
	 *参考
	 *http://arc360.info/algo/privatekey.html
	 */

	/**
	 * extende_Euclid(1,0,a,0,1,b)
	 * が最初に代入する値。
	 * ax+by=gcd(a,b)を満たす、(x,y)とgcd(a,b)を
	 * {x,y,gcd(a,b)}の形で返す。
	 * ただし、a>bとする。
	 */
	long[] extended_Euclid(long x0,long y0,long c0,long x1,long y1,long c1){
		if(c0<c1)return extended_Euclid(x1,y1,c1,x0,y0,c0);
		if(c1==0)return new long[]{x0,y0,c0};
		else{
			long q=c0/c1;
			return extended_Euclid(x1,y1,c1,x0-x1*q,y0-y1*q,c0-c1*q);
		}
	}

}
0