素数打表

获取MAXN内的所有质数, 百万数量级内有效

bool nprime[MAXN];
vector <int> prime;

void get_prime() {
	memset(nprime, 0, sizeof(nprime));
	nprime[1] = 1;
	for (int i=2; i*i<MAXN; i++) {
		if (!nprime[i]) {
			for (int j=i*i; j<MAXN; j+=i) {
				nprime[j] = true;
			}
		}
	}
	for (int i=2; i<MAXN; i++) {
		if (!nprime[i]) {
			prime.push_back(i);
//			cout << i << endl;
		}
	}
}

快速分解质因数n，$O(logn)$

int mpf[N];//mpf[i] i的 min prime factor
void getmpf() {//获取N以内所有数的最小质因子
    memset(mpf, 0, sizeof(mpf));
    int sz = sqrt(N);
    for (int i=2; i<=sz; i++) {
        if (mpf[i]) continue;
        for (int j=i*i; j<N; j+=i) {
            mpf[j] = i;
        }
    }
    for (int i=2; i<N; i++) {
        if (mpf[i] == 0) mpf[i] = i;//质数的最小质因子是本身
    }
    // for (int i=0; i<N; i++) {
    //     cout << i << "=" << mpf[i] << ", ";
    // }
}

//打印x所分解的质因数
for (int i=x; i>1; i = i/mpf[i]) {
    cout << mpf[i] << " ";
}

欧拉函数

phi[n]=不大于n且与n互质的正整数个数 1到n内所有phi，$O(nlogn)$

ll phi[MAXN];
void phi_table(int n) {
	memset(phi, 0, sizeof(phi));
	phi[1] = 1;
	for (int i=2; i<=n; i++) if (!phi[i])//i是素数
	for (int j=i; j<=n; j+=i) {
		if (!phi[j]) phi[j] = j;
		phi[j] = phi[j]/i*(i-1);//先除后乘防溢出
	}
}

phi(n), $O(\sqrt n)$

int euler_phi(int n) {
	int m = (int) sqrt(n+0.5);
	int ans = n;
	for (int i=2; i<=m; i++) {
		if (n%i == 0) {
			ans = ans / i * (i-1);
			while (n%i == 0) n/=i;
			if (n == 1) break;
		}
	}
	if (n != 1) ans = ans / n * (n-1);
	return ans;
}

欧几里得

a与b最大公约数

ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a%b);
}

拓展欧几里得

解方程a * x + b * y = d 即 ax = d (mod b), 其中d=gcd(a,b) 整数解有d个: x, x+b/d, .., x+(d-1)b/d 若求a * x + b * y = c, 先求得a * x + b * y = gcd(a,b) 若c%gcd(a,b)=0则有解, 有d个解:x0=c/gcd(a,b)* x%b, x0+b/d, ..., x0+(d-1)b/d

void ex_gcd(ll a, ll b, ll* d, ll* x, ll* y) {
	if (b == 0) {
		*d = a;
		*x = 1;
		*y = 0;
	}
	else {
		ex_gcd(b, a%b, d, x, y);
		ll t = *x;
		*x = *y;
		*y = t - (a/b)*(*y);
	}
}

乘法逆元

拓展欧几里得求逆元

// a*x = 1 (mod n) -> a*x + n*y = 1
ll inv(ll a, ll n) {
	ll x, y, d;
	ex_gcd(a, n, x, y, d);
	return d == 1 ? (x+n)%n : -1;
}

费马小定理求逆元, 要求模的是素数