「素数」を編集中 (節単位)

==素数を使った問題==
[[競技プログラミング]]においては、道順などの求めたい数を100,000,007などの素数で割った数を出力させる問題が出題されることがある。
素数で割った余りを扱う際には、[[逆元]](割る数をMとしたとき、a*xをMで割った余りが1になるようなxをaの逆元という)が簡単に計算できるので、都合がいい。

逆元を求めるのには拡張[[ユークリッドの互除法]]を使うのがいいとされているが、
そんな複雑なことをしなくても累乗の計算をするだけでとりあえず求めることができる。
<source lang="c">
#define MOD_BY 100000007

int getGyakugen(int a) {
	int zyou=MOD_BY-2;
	int result=1;
	while(zyou>0) {
		if(zyou&1)result=(int)((long long)result*a%MOD_BY);
		zyou>>=1;
		a=(int)((long long)a*a%MOD_BY);
	}
	return result;
}
</source>