快速幂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))