逆元

1 mod_inverse.cpp

#include<iostream>
using namespace std;
typedef long long ll;

const int mod = 1000000007;

int ex(int x, int t) {
	if (t == 0) return 1;
	ll res = ex(x, t >> 1);
	(res *= res) %= mod;
	if (t & 1) (res *= x) %= mod;
	return res;
}
int fermat(int x) {
	return ex(x, mod - 2);
}

int RHO(int x) {
	if (x == 1) return 1;
	int rem = mod % x;
	if (rem < (x >> 1)) return (ll)RHO(rem) * (mod - mod / x) % mod;
	else return (ll)RHO(x - rem) * (mod / x + 1) % mod;
}

int main(){
	int x;
	cin >> x;
	int inv1 = fermat(x);
	int inv2 = RHO(x);
	printf("inverse of %d (mod 10^9+7)\n", x);
	printf("by fermat theorem     : %d : (%d * %d) = %lld (= %lld (mod 10^9+7))\n",
		   inv1, x, inv1, (ll)x * inv1, ((ll)x * inv1) % mod);
	printf("by rng-hos-ome scheme : %d : (%d * %d) = %lld (= %lld (mod 10^9+7))\n",
		   inv2, x, inv2, (ll)x * inv2, ((ll)x * inv2) % mod);
	return 0;
}

2 bench.txt

Caluculate 100000000 inverses by fermat theorem     : 27943 ms
Caluculate 100000000 inverses by rng-hos-ome scheme : 19909 ms

3 bench.cpp

#include<iostream>
#include<sys/time.h>
using namespace std;
typedef long long ll;
// Time
ll getTime() {
    struct timeval tv;
    gettimeofday(&tv, NULL);
    ll result =  tv.tv_sec * 1000LL + tv.tv_usec / 1000LL;
    return result;
}
ll start_time;
void setTime(){ start_time = getTime();}
ll nowTime(){ return getTime() - start_time;}
//

const int mod = 1000000007;

int ex(int x, int t) {
	if (t == 0) return 1;
	ll res = ex(x, t >> 1);
	(res *= res) %= mod;
	if (t & 1) (res *= x) %= mod;
	return res;
}
int fermat(int x) {
	return ex(x, mod - 2);
}

int RHO(int x) {
	if (x == 1) return 1;
	int rem = mod % x;
	if (rem < (x >> 1)) return (ll)RHO(rem) * (mod - mod / x) % mod;
	else return (ll)RHO(x - rem) * (mod / x + 1) % mod;
}

int main(){
	int n, avoid_O2;
	cin >> n;
	printf("Caluculate %d inverses by fermat theorem     : ", n);
	fflush(stdout);
	setTime();
	for (int i = 1; i <= n; ++i) avoid_O2 += fermat(i);
	printf("%lld ms\n", nowTime());
	
	printf("Caluculate %d inverses by rng-hos-ome scheme : ", n);
	fflush(stdout);
	setTime();
	for (int i = 1; i <= n; ++i) avoid_O2 += RHO(i);
	printf("%lld ms\n", nowTime());
	return avoid_O2;
}