フェルマーの小定理とmod、二項係数など（仮・メモ）
10^9+7で割ったあまり問題
逆元の求め方
#include <stdio.h> long long modpow(long long a, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } // a^{-1} mod を計算する long long modinv(long long a, long long mod) { return modpow(a, mod - 2, mod); } int main(void){ // mod. 13 での逆元を求めてみる int i; for (i = 1; i < 13; ++i) { printf("%d's inv: %d\n",i,modinv(i,13)); } return 0; }
