人工的過ぎる設定であまり自然じゃない問題だけど、整数の整除についての注意点を学べる教育的良問ですね。

問題概要

整数 $n$ が与えられる。 $2$ を $n$ 回二乗した数より大きい最小の素数を $p$ とする。

$111...1 (1 が p-1 個)$ を $p$ で割ったあまりを求めよ。

制約

$0\le n$ < 1000

考えたこと

$n=0$ のとき $p=2$
$n=1$ のとき $p=3$
$n=2$ のとき $p=5$
$n=3$ のとき $p=17$
...

である。11111...1 (1 が $p-1$ 個) といったレピュニット数は、

$\frac{10^{p-1} - 1}{9}$

と考えることで扱いやすくなる。こういう式になると、 $a$ と $p$ が互いに素なときに $a^{p-1} ≡ 1$ (mod. p) が成立するという Fermat の小定理が使えそうである。すなわち、 $10^{p-1} - 1$ が $p$ の倍数になるから答えは 0 になりそうである。ただし 2 つ注意点があり

10 と $p$ が互いに素かどうか
9 で割るときに、9 と $p$ が互いに素かどうか (互いに素なら

$n \ge 3$ であれば、両方満たすので答えは 0 でよい。 $n \le 2$ のときはちゃんと計算する。

#include <iostream>
using namespace std;

int main() {
  int n; cin >> n;
  if (n == 0) cout << 1 << endl;
  else if (n == 1) cout << 2 << endl;
  else if (n == 2) cout << 1 << endl;
  else cout << 0 << endl;
}

けんちょんの競プロ精進記録

競プロの精進記録や小ネタを書いていきます

AOJ 2610 Fast Division (JAG 夏合宿 2013 day3-D) (250 点)

問題概要

制約

考えたこと