GCD类模板

快速幂1

ll quickpow(ll x, ll y, ll mod)
{
	if (y == 0)return 1;
	if (y == 1)return x % mod;
	else
	{
		if (y % 2 == 0)
		{
			ll t = quickpow(x, y / 2, mod);
			return (t * t)%mod;
		}
		else
		{
			ll t = quickpow(x, y / 2, mod);
			t = (t * t)%mod;
			return (t * (x%mod)) % mod;
		}
	}
}

快速幂2

ll quickpow(ll x, ll y,ll mod) {
	ll ans = 1; x %= mod;
	while (y) {
		if (y & 1)ans = ans * x%mod;
		x = x * x%mod;
		y >>= 1;
	}
	return ans;
}

扩展欧几里得算法

ll exgcd(ll a, ll b, ll &x, ll &y) {
	if (!b) {
		x = 1, y = 0;
		return a;
	}
	int d = exgcd(b, a%b, y, x);
	y -= a / b * x;
	return d;
}

欧拉函数1（直接求解欧拉函数）

ll euler(ll n) { //返回euler(n)     
	ll res = n, a = n;
	for (ll i = 2; i*i <= a; i++) {
		if (a%i == 0) {
			res = res / i * (i - 1);//先进行除法是为了防止中间数据的溢出     
			while (a%i == 0) a /= i;
		}
	}
	if (a > 1) res = res / a * (a - 1);
	return res;
}

欧拉函数2（快）

void Euler(){
    phi[1] = 1;
    for(int i = 2; i < N; i ++){
        if(!phi[i]){
            for(int j = i; j < N; j += i){
                if(!phi[j]) phi[j] = j;
                phi[j] = phi[j] / i * (i-1);
            }
        }
    }
}

欧拉函数3（更快）

#include <bits/stdc++.h>
const int N = 1e7 + 10;
#define ll long long
using namespace std;
int prime[N], cnt, phi[N], n;//prime[0]=2,cnt表示小于等于n有几个质数
bool st[N];
void Euler(int n)
{
	phi[1] = 1;
	for (int i = 2; i <= n; i++)
	{
		if (!st[i])
		{
			prime[cnt++] = i;
			phi[i] = i - 1;
		}
		for (int j = 0; prime[j] <= n / i; j++)
		{
			int t = prime[j] * i;
			st[t] = true;
			if (i%prime[j] == 0)
			{
				phi[t] = phi[i] * prime[j];
				break;
			}
			phi[t] = phi[i] * (prime[j] - 1);
		}
	}
}

整点问题

平面直角坐标系上，(a,b)和（c,d）点之间有  gcd（a-c,b-d）-1  个整点 (不包括(a,b),(c,d))