なぜかもとの整数と掛けても1にならない数が出てくることがあります。
#include <stdio.h>
/* this is prime */
#define MOD_BY 100000007
int getInv(int x) {
int nowzyou=MOD_BY-2;
long long now=x;
long long result=1;
while(nowzyou>0) {
if(nowzyou & 2)result=(result*now)%MOD_BY;
now=(now*now)%MOD_BY;
nowzyou>>=1;
}
return (int)result;
}
int main(void) {
int i;
for(i=1;i<100;i++) {
printf("%10d %10d %10d\n",i,getInv(i),(int)(((long long)i*getInv(i))%MOD_BY));
}
return 0;
}
3番目が全て1になってほしいのですが、100000006が混ざってしまいます。
フェルマーの小定理についてはここを参考にしました。
http://www2.cc.niigata-u.ac.jp/~takeuch ... ermat.html
やっぱり整数の逆元を求めるには、拡張ユークリッドの互除法を用いなければならないのでしょうか?
よろしくお願いします。