时间复杂度：

$O(n^2)$

$O(n~log_2~n)$

$O(n)$

$O(log_2~n)$

……

中国剩余定理

#include <iostream>
#include <algorithm>
using namespace std;

long long a, b, c, d, e, f;

long long exgcd(long long a, long long b, long long& x, long long& y)
{
	if (b == 0)
	{
		x = 1, y = 0;
		return a;
	}
	long long ret = exgcd(b, a % b, y, x);
	y -= a / b * x;
	return ret;
}

long long getInv(long long a, long long mod)
{
	long long x, y;
	long long d = exgcd(a, mod, x, y);
	return d == 1 ? (x % mod + mod) % mod : -1;
}

long long lcm()
{
	return a * b / __gcd(a, b) * c / __gcd(a * b / __gcd(a, b), c);
}

long long answer()
{
	long long n = lcm(), aa = getInv(n / a, a), bb = getInv(n / b, b), cc = getInv(n / c, c);
	if (((n / a * aa * d) + (n / b * bb * e) + (n / c * cc * f)) % n == 0) return n;
	return ((n / a * aa * d) + (n / b * bb * e) + (n / c * cc * f)) % n;
}

int main()
{
	cout << "请输入六个数字，请保证前三个数不为零且互质\n";
	cin >> a >> b >> c >> d >> e >> f;
	if (!a || !b || !c) return 0;
	cout << answer();
}

快速冥

#include <iostream>
using namespace std;

long long qmi(long long a, long long k, long long p)//快速冥函数
{
	long long res = 1;//初始时赋成1，k=0也不会出错因为任何数的0次幂等于0
	while (k)//当遍历完k是跳出
	{
		if (k & 1) res = res * a % p;//只有k的末尾是1时才算进去
		k >>= 1;//将k右移一位，使末尾往前移
		a = a * a % p;//更新a^(2^n)
	}
	return res;
}

int main()
{
	long long b, p, k;
	cin >> b >> p >> k;
	cout << b << '^' << p << " mod " << k << " = " << qmi(b, p , k);
	return 0;
}