算法基础课程 数学知识(二)
一、欧拉函数
公式及其简单的证明
欧拉定理
若\(a\)与\(n\)互质,则有\(a^{\phi(n)} \equiv 1 (mod \quad n)\)
简单证明
定义求欧拉函数
时间复杂度\(O(\sqrt{n})\)
int phi(int n)
{
int res = n;
for (int i = 2; i <= n / i; ++ i)
{
if (n % i == 0)
{
res = res / i * (i - 1);
while (n % i == 0) n /= i;
}
}
if (n > 1) res = res / n * (n - 1);
return res;
}
筛法求欧拉函数
若\(i\)为质数,则\(\phi(i) = i - 1\);
若\(i\)不为质数,且\(prime[j]\)为\(i\)的约数,则\(\phi(i) = primes[j] * \phi(i)\);
若\(i\)不为质数,且\(primes[j]\)不为\(i\)的约数,则\(\phi(i) = (primes[j] - 1) * \phi(i)\);
特别情况下,当\(i\)为1时,\(\phi = 1\)
时间复杂度\(O(n)\)
void euler(int n)
{
phi[1] = 1;
for (int i = 2; i <= n; ++ i)
{
if (!st[i]) primes[cnt ++ ] = i, phi[i] = i - 1;
for (int j = 0; primes[j] <= n / i; ++ j)
{
st[primes[j] * i] = 1;
if (i % primes[j] == 0)
{
phi[i * primes[j]] = phi[i] * (primes[j]);
break;
}
phi[i * primes[j]] = phi[i] * (primes[j] - 1);
}
}
}
二、快速幂
时间复杂度\(O(logn)\)
int qpow(int a, int k, int mod)
{
int res = 1;
a %= mod;
while (k)
{
if (k & 1) res = res * a % mod;
k >>= 1;
a = a * a % mod;
}
return res;
}
三、求逆元
\(a\)、\(p\)互质,\(a \cdot a^{-1} \equiv 1 (mod \quad p)\),在取余意义下,除以一个数等价于乘以这个数的逆元
若\(p\)为质数,\(a^{-1} = a^{p - 2}\);
若\(p\)不为质数,利用扩展欧几里得算法求\(a^{-1}\)
例题:AcWing 快速幂求逆元
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b, ll mod)
{
ll ans = 1;
a %= mod;
while (b)
{
if (b & 1) ans = ans * a % mod;
a = a * a % mod;
b >>= 1;
}
return ans;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
while (n -- )
{
ll a, p;
cin >> a >> p;
if (a % p) cout << gcd(a, p - 2, p) << '\n';
else cout << "impossible\n";
}
return 0;
}
四、裴蜀定理
对于任意正整数\(a\)、\(b\),一定存在非零整数\(x\)、\(y\),使得\(ax + by = gcd(a, b)\),所有\(a\)和\(b\)所能凑出来的数一定很为\(gcd(a, b)\)的倍数
五、扩展欧几里得算法
给定正整数\(a\)、\(b\),求一组\(x\)、\(y\)使得\(ax + by = gcd(a, b)\)
时间复杂度\(O(logn)\)
int exgcd(int a, int b, int &x, int &y)
{
if (!b)
{
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
六、线性同余方程
给定\(a\)、\(b\)、\(m\),求出一个 \(x\),使其满足 \(ax \equiv b (mod \quad m)\)
时间复杂度\(O(logn)\)
例题:AcWing 线性同余方程
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll exgcd(ll a, ll b, ll &x, ll &y)
{
if (!b)
{
x = 1, y = 0;
return a;
}
ll d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n;
cin >> n;
while (n -- )
{
ll a, b, m, x, y;
cin >> a >> b >> m;
ll d = exgcd(a, m, x, y);
if (b % d) cout << "impossible\n";
else cout << x * b / d % m << '\n';
}
return 0;
}
七、中国剩余定理
原文地址:https://www.cnblogs.com/Panmaru/p/17267036.html