1 月 22 日代码

int gcd(int a, int b) {
	return !b ? a : gcd(b, a % b); 
}

void exgcd(int a, int b, int &g, int &x, int &y) {
	if (!b) g = a, x = 1, y = 0;
	else exgcd(b, a % b, g, y, x), y -= x * (a / b);
}

long long pow(long long a, long long n, long long p) {
	long long res = 1;
	for (; n; n >>= 1, a = a * a % p) if (n & 1) res = res * a % p;
	return res;
}

long long pow(long long a, long long n, long long p) {
	if (n == 0) return 1;
	if (n % 2 == 0) {
		long long x = pow(a, n / 2, p);
		return x * x % p;
	} else return a * pow(a, n - 1, p) % p;
}

int inv(int a, int p) {
	int g, res, tmp;
	exgcd(a, p, g, res, tmp);
	return (res % p + p) % p;
}

int inv(int a, int p) {
	return pow(a, p - 2, p);
}

const int MAXN = 1e6;

bool isNotPrime[MAXN + 1];
int primes[MAXN + 1], primeCnt;

void sieve() {
	isNotPrime[1] = true;
	for (int i = 2; i <= MAXN; i++) {
		if (!isNotPrime[i]) {
			primes[++primtCnt] = i;
		}
		
		for (int j = 1; j <= primeCnt && i * primes[j] <= MAXN; j++) {
			isNotPrime[i * primes[j]] = true;
			if (i % primes[j] == 0) break;
		}
	}
}