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

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

AOJ 2610 Fast Division

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

問題へのリンク

問題概要

整数  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;
}