結果

問題 No.109 N! mod M
ユーザー 37zigen
提出日時 2016-05-03 15:34:09
言語 Java
(openjdk 23)
結果
WA  
実行時間 -
コード長 2,906 bytes
コンパイル時間 2,560 ms
コンパイル使用メモリ 78,832 KB
実行使用メモリ 54,612 KB
最終ジャッジ日時 2024-10-05 03:42:04
合計ジャッジ時間 4,258 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 5 WA * 4
権限があれば一括ダウンロードができます

ソースコード

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();
			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)){
			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;
			for(long i=m-1;i>=n+1;i--){
				long a=ans*inverse_element((int)i, (int)m);
				while(a<0)a+=m;
				ans=ans*a;
				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が素数でないときは逆元は存在しない(正しくない値を返す)。
	 * 拡張ユークリッドの控除法を用いた。
	 */
	int inverse_element(int a,int p){
		return extended_Euclid(a, 0, 1, 0, p, 1)[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とする。
	 */
	int[] extended_Euclid(int x0,int y0,int c0,int x1,int y1,int c1){
		if(c0<c1)return extended_Euclid(x1,y1,c1,x0,y0,c0);
		if(c1==0)return new int[]{x0,y0,c0};
		else{
			int q=c0/c1;
			return extended_Euclid(x1,y1,c1,x0-x1*q,y0-y1*q,c0-c1*q);
		}
	}

}
0