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

ヘクトのメモ

なんとなくいろいろ書いていくと思います.

AOJ 2610 Fast Division

この問題はネタバレ要注意です.

問題文
http://judge.u-aizu.ac.jp/onlinejudge/description.jsp?id=2610


解法
式を整理すると,{ \displaystyle  \frac{10^{p(n)-1}-1}{9}  \mod p(n) }
ここで,フェルマーの小定理を考える.
{ \displaystyle 10^{p(n)-1} \equiv 1  \mod p(n) } より,式の分子が0になる.
{ \displaystyle 0 \le n \le 2   } の時には,{ \displaystyle p(n) }が分子の10または分母の9と互いに素ではない.
よって,この3ケースは例外である.
ただし,コーナーケースはサンプルに全部乗っているので,そのまま出力.

ソースコードは以下の通り

int main(void){
	int n;
	cin >> n;
	if(n==0)
		puts("1");
	else if(n==1)
		puts("2");
	else if(n==2)
		puts("1");
	else
		puts("0");
	return 0;
}

2015.09.17 閲覧数が多いので,数式をtexで書き直した.