RandomGCD.cpp

#define _USE_MATH_DEFINES
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <climits>
#include <cfloat>
#include <ctime>
#include <cassert>
#include <map>
#include <utility>
#include <set>
#include <iostream>
#include <memory>
#include <string>
#include <vector>
#include <algorithm>
#include <functional>
#include <sstream>
#include <complex>
#include <stack>
#include <queue>
#include <numeric>
#include <list>

using namespace std;
typedef long long ll;
const int MOD = 1000000007;
const int INF = 100000000; //1e8

typedef long long ll;
typedef pair<int, int> Pii;
typedef pair<ll, ll> Pll;

#define FOR(i,n) for(int i = 0; i < (n); i++)
#define sz(c) ((int)(c).size())
#define ten(x) ((int)1e##x)
#define tenll(x) ((ll)1e##x)

template<class T> ll mod_pow(T a, T n, T mod){
	ll ret = 1;
	ll p = a % mod;
	while (n){
		if (n & 1) ret = ret * p % mod;
		p = p * p % mod;
		n >>= 1;
	}
	return ret;
}

const int N = ten(6) + 10;
int mobius[N];
void init_mobius(){
	mobius[1] = 1;
	for (int i = 2; i < N; i++){
		int u = 1 - mobius[i];
		mobius[i] = -u;
		if (u) for (int j = 2 * i; j < N; j += i) mobius[j] += u;
	}
}

class RandomGCD {
public:
	int countTuples(int N, int K, int low, int high) {
		memset(mobius, 0, sizeof(mobius));
		init_mobius();

		low = (low + K - 1) / K;
		high = high / K;
		ll ans = 0;
		for (int i = 1; i < ten(6) + 1; i++){
			int a = high / i - (low - 1) / i;
			ll g = mod_pow<ll>(a, N, MOD) - a;
			ans += g * mobius[i];
		}
		if (low <= 1 && 1 <= high) ans++;

		return (ans % MOD + MOD) % MOD;
	}

};

// BEGIN CUT HERE
#include <ctime>
#include <sstream>
#include <fstream>
double start_time; string timer()
{
	ostringstream os; os << " (" << int((clock() - start_time) / CLOCKS_PER_SEC * 1000) << " msec)"; return os.str();
}
template<typename T> ostream& operator<<(ostream& os, const vector<T>& v)
{
	os << "{ ";
	for (typename vector<T>::const_iterator it = v.begin(); it != v.end(); ++it)
		os << '\"' << *it << '\"' << (it + 1 == v.end() ? "" : ", "); os << " }"; return os;
}
void verify_case(const int caseno, const int&N, const int&K, const int&low, const int&high, const int& Expected, bool verbose = false) {
	int Received = RandomGCD().countTuples(N, K, low, high);
	cerr << "Test Case #" << caseno << "...";
	bool ok = (Expected == Received);
	if (ok) cerr << "PASSED" << timer() << endl;   else {
		cerr << "FAILED" << timer() << endl;
		if (verbose) cerr << "\tN: " << N << endl;
		if (verbose) cerr << "\tK: " << K << endl;
		if (verbose) cerr << "\tlow: " << low << endl;
		if (verbose) cerr << "\thigh: " << high << endl;
		cerr << "\to: \"" << Expected << '\"' << endl << "\tx: \"" << Received << '\"' << endl;
	}
}
void notify_memory_usage(){
#ifndef _WIN32
	std::ifstream ifs("/proc/self/status", std::ios_base::in);
	std::string str;
	for (;;){
		std::getline(ifs, str);
		if (str.find("VmPeak") != std::string::npos){ cout << str << " (< 64MB)" << endl; }
		if (str.find("VmStk") != std::string::npos){ cout << str << " (< 8MB)" << endl; break; }
	}
#endif
}
#define CASE(N) if (N==runno_ || (runno_<0 && N+1>=-runno_)) {int caseno=N; start_time=clock();
#define RUN_TEST()	 verify_case(caseno, N, K, low, high, _, verbose_);}
int main(int argc, char **argv){
	bool verbose_ = false;
	int runno_ = -1;
	if (argc >= 2) if (!strcmp(argv[1], "-v")) verbose_ = true;
	if (argc == 2 && !verbose_) runno_ = atoi(argv[1]);
	else if (argc == 3 && verbose_) runno_ = atoi(argv[2]);
	CASE(6){
		int N = 2;
		int K = 5;
		int low = 500000;
		int high = 500005;
		int _ = 2;
		RUN_TEST();
	}
	CASE(7){
		int N = 1000000000;
		int K = 2;
		int low = 999900000;
		int high = 1000000000;
		int _ = 403668037;
		RUN_TEST();
	}
	CASE(-1){
		int N = 3;
		int K = 1;
		int low = 6;
		int high = 8;
		int _ = 18;
		RUN_TEST();
	}
	CASE(0){
		int N = 2;
		int K = 2;
		int low = 2;
		int high = 4;
		int _ = 3;
		RUN_TEST();
	}
	CASE(1){
		int N = 2;
		int K = 100;
		int low = 2;
		int high = 4;
		int _ = 0;
		RUN_TEST();
	}
	CASE(2){
		int N = 1;
		int K = 5;
		int low = 5;
		int high = 5;
		int _ = 1;
		RUN_TEST();
	}
	CASE(3){
		int N = 73824;
		int K = 17347;
		int low = 9293482;
		int high = 9313482;
		int _ = 0;
		RUN_TEST();
	}
	CASE(4){
		int N = 222;
		int K = 222;
		int low = 222;
		int high = 22222;
		int _ = 339886855;
		RUN_TEST();
	}
	notify_memory_usage();

}
// END CUT HERE