yukicoder : No.109 N! mod M

いかにもこの作者さん、という感じの問題。
http://yukicoder.me/problems/120

問題

N,Mの２値で構成されるT個のクエリが与えられる。
各クエリに対しN! % Mを答えよ。

なお、である。

解法

N≧Mな時は明らかに0である。
また、Nが小さいときは実際にN回ループを回せばよい。

問題はいずれでもない、Mが結構大きい場合である。
ここはNが割とMに近いことを利用する。

• Mが素数の場合
  • (M-1)! == M-1 (mod M)なので、N! * ((M-1)!/N!) == M-1 (mod M)
  • よってN! == (M-1) * ((M-1)!/N!)^(-1) (mod M)
  • NはMと近いので、((M-1)!/N!)は(N+1)～(M-1)までループを回して掛け合わせればよい。
• Mが合成数の場合
  • Mが合成数なら、最小の素因数をpとすると(M/p)!まで掛け合わせればMの剰余が0になるので、N≧M/pなら答えは0。
    • 実際はpが何であってもMが合成数なら(M/2)!まで掛ければ剰余が0になるので、以下のコードはN≧M/2で判定している。
  • N＜M/2の場合、Mが2*10^5以下でNは10^5以下なので、N回ループ回しても間に合う。

ll modpow(ll a, ll n, ll mo) {
	ll r=1;
	while(n) r=r*((n%2)?a:1)%mo,a=a*a%mo,n>>=1;
	return r;
}

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	int T;
	cin>>T;
	while(T--) {
		ll N,M;
		cin>>N>>M;
		if(N>=M || M==1) {
			_P("0\n");
			continue;
		}
		if(N<=300000) {
			ll a=1;
			for(i=1;i<=N;i++) a=(a*i)%M;
			_P("%lld\n",a);
			continue;
		}
		
		ll pp;
		for(pp=2;pp*pp<=M;pp++) if(M%pp==0) break;

		if(M%pp) {
			ll a=1;
			for(i=N+1;i<=M-1;i++) a=(a*i)%M;
			_P("%lld\n",(M-1)*modpow(a,M-2,M)%M);
		}
		else {
			_P("0\n");
		}
	}
}

まとめ

Nの値域が妙に大きいので、(N+1)～(M-1)の積を使うことはすぐに思いついたけど、そこから色々バグを仕込んで手間取った。