「ディバイド・アウト」問題
締め切りが 2017/09/07 10:00 AM なので,その 1 分後に投稿されるように予約
設問
自然数 n と素数 p に対し、n の階乗(n!)を p でこれ以上割り切れなくなるまで繰り返し割り、
その商をさらに p で割ったときの余りを F(n, p) と定義します。
例えば F(12, 5)=4 です。
12!(=479001600)は 5 で最大 2 回割ることができます。その商は 19160064 です。
さらにこれを 5 で割った余りは 4 です。
同様に、F(5, 3)=1, F(20, 7)=5, F(1000, 31)=11 となることが確かめられます。
標準入力から、自然数 n と素数 p (1 ≦ n ≦ 10^12, 1 ≦ p ≦ 10^5)が半角空白区切りで与えられます。
標準出力に F(n, p) の値を出力するプログラムを書いてください。
================================================================================
# ウィルソンの定理より
# (n %% 2*p)!≡n! mod p
1 〜 n の整数のうち p を因数としてもたない数を掛け合わせる求める関数を g(n, p) と表記すると,
n = 916554098334, p = 99961 では,
g(916554098334, 99961) = g(916554098334 %% (2*99961), 99961) = g(93858, 99961) …… (a)
1 〜 n の整数のうち,99961 を因数として持つ数は 99961*(1, 2, ..., 916554098334 %/% 99961) = 9961*(1, 2, ..., 9169116)
n = 9169116 として,
1 〜 n について,再度 g(9169116, 99961) = g(9169116 %% (2*99961), 99961) = g(172626, 99961) …… (b)
1 〜 n の整数のうち,99961 を因数として持つ数は 99961*(1, 2, ..., 9169116 %/% 99961) = 9961*(1, 2, ..., 91)
n = 91 として,再度 g(91, 99961) であるが,これは,99961 の因数は含まれないので,普通の階乗 …… (c)
(a), (b), (c) を掛け合わせたものが g(916554098334, 99961)。
なお,途中の掛算は p を法として行う。
f = function(n, p) {
ans = 1
while (n != 0) {
for (i in 1:(n %% (2*p))) {
if (i %% p != 0) {
ans = (ans*i) %% p
}
}
n = n %/% p
}
cat(ans)
}
# arg = scan(file("stdin", "r"))
# f(arg[1], arg[2])
f(5, 3) # 1
f(30, 11) # 10
f(130, 13) # 6
f(321200, 307) # 124
f(8800, 99397) # 23239
f(98765432170, 17) # 8
f(916554098334, 99961) # 18502