結果

問題 No.2326 Factorial to the Power of Factorial to the...
ユーザー ID 21712
提出日時 2025-05-06 00:50:13
言語 Go
(1.23.4)
結果
AC  
実行時間 3 ms / 2,000 ms
コード長 937 bytes
コンパイル時間 12,473 ms
コンパイル使用メモリ 237,880 KB
実行使用メモリ 6,272 KB
最終ジャッジ日時 2025-05-06 00:50:27
合計ジャッジ時間 13,701 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

package main

import . "fmt"
import . "math/big"

func main() {
	var n, p int
	Scan(&n,&p)
	
	if n < p {
		Println(0)
		return
	}
	
	// n! を p で割る回数、1 ... n まで p で割れる回数を合算す
	var cnt int
	for i := 1; i <= n; i++ {
		for x := i; x % p == 0; cnt, x = cnt + 1,  x / p {}
	}
	
	const Mod int = 1e9 + 7
	
	// 答えは cnt の n!^n! 倍
	// ans = cnt * n!^n! (mod 1e9+7)
	// M = 1e9+7
	// gcd(n!,M) = 1
	// n! = F * M + A (A < M)
	// n! = G * (M-1) + B (B < M-1)
	// とおく
	// フェルマーの小定理より n!^(M-1) = 1 (mod M)
	// n!^n! = n!^(G*(M-1)+B) (mod M)
	//       = n!^(G*(M-1)) * n!^B (mod M)
	//       = (n!^(M-1))^G * n!^B (mod M)
	//       = n!^B (mod M)
	//       = A^B (mod M)
	
	a, b := 1, 1
	for i := 1; i <= n; i++ {
		a = a*i%Mod
		b = b*i%(Mod-1)
	}
	
	e := int(new(Int).Exp(NewInt(int64(a)),NewInt(int64(b)),NewInt(int64(Mod))).Int64())
	
	ans := cnt*e%Mod
	
	Println(ans)
	
}
0