「ディバイド・アウト」問題

「ディバイド・アウト」問題

締め切りが 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