読者です 読者をやめる 読者になる 読者になる

pekempeyのブログ

競技プログラミングに関する話題を書いていきます。

Number Theory

Codeforces Round #395 (Div. 1) C. Timofey and remoduling (modsqrt)

http://codeforces.com/contest/763/problem/C

mod 平方根

素数 mod p で となる を見つけるアルゴリズムです。Cipolla のアルゴリズムというのを紹介します。Cipolla's algorithm - Wikipedia

CodeForces Round #382 (Div. 1): B. Taxes

http://codeforces.com/contest/736/problem/B 問題概要 $n$円の収入に対して、$n$未満の最大の約数だけ税金がかかる。後の説明のために税金額を$f(n)$と書くことにする。 Mr. Funt は税金の額をごまかすために、$n$をいくつかの整数$n_1,n_2,\ldots,n_k$に…

yukicoder 443: GCD of Permutation

http://yukicoder.me/problems/no/443

素数冪 mod における階乗の周期性

概要 素数 mod における階乗の周期性は Wilson の定理としてよく知られている。 Wilson の定理:$p$ が素数であるとき、かつそのときに限り $(p-1)! \equiv p-1\;(\mathrm{mod}\; p)$ $p!\equiv0$ は当然であるため、この記事では階乗は既約のものを扱う。す…