初等数论（一）

初等数论

素数筛

在筛时用lp[i]存储i的最小素因子，可加速唯一分解​

void getprime()
{
	idx = 0;
	for (int i = 2; i <= maxn; i++)
	{
		if (!lp[i]) prime[++idx] = lp[i] = i;
		for (int j = 1; j <= idx && prime[j] <= lp[i] && i * prime[j] <= maxn; j++)
			lp[i * prime[j]] = prime[j];
	}
}

唯一分解定理

div数组存放素因子与其出现次数

void solve(long long x)
{
	if (x == 0) return;
	for (int i = 1;i <= idx;++i)
	{

		if (prime[i] > x)
			break;
		int cnt = 0;
		if (x < maxn) { //最小素因子已经求出，无需继续遍历
			while (x != 1) {
				int temp = x;
				cnt = 0;
				while (temp % lp[x] == 0)
					temp /= lp[x], cnt++;
				divs[len++] = { lp[x],cnt };
				x = temp;
			}
			break;
		}
		while (x % prime[i] == 0)
		{
			x /= prime[i];
			cnt++;
		}
		if (cnt)
			divs[len++] = { prime[i],cnt };
	}
	if (x > 1)
		divs[len++] = { x,1 };
}

扩展欧几里得算法

扩展$gcd$算法，$d$是$a$与$b$的最大公约数，$ax+by=d$，其中$|x|+|y|$最小​

typedef long long ll;
void egcd(ll a, ll b, ll& d, ll& x, ll& y)
{
    if (!b) { d = a;x = 1;y = 0; }
    else { egcd(b, a % b, d, y, x);y -= x * (a / b); }
}

存在方程$ax+by=c$，且 $x,y,c$ 为整数
上述方程有解的充要条件是 $gcd(a,b)|c$ （裴蜀定理）,利用扩展欧几里得算法可以求得方程的解。

若其中一组解为$(x_0,y_0)$ ,它的任意整数解都可以写成 $(x_0+kb',y_0-ka')$ ,其中 $a'=a/gcd(a,b)$,$b'=b/gcd(a,b)$。

理解​：

当 $b=0$时，$gcd(a,b)=a$,$ax+by=a$,可得$x=1$,$y=0$

否则，$ax_1+by_2=gcd(a ,b)=gcd(b, a\%b)=bx_2+a\%by_2$

$bx_2+a\% by_2 =bx_2+(a-b(a/b))y_2=bx_2+ay_2-b(a/b)y_2=ay_2+b(x_2-y2(a/b))$

即 ：$ax_1+by_2=ay_2+b(x_2-y2(a/b))$

由此可得, $x_1=y2,y1=x2-y2(a/b)$

扩展欧几里得算法求乘法逆元

ll inv(ll a, ll n)
{
    ll d, x, y;
    egcd(a, n, d, x, y);
    return d == 1 ? (x + n) % n : -1;
}//计算模n下a的逆

若存在 $a^{-1}$ ，使得 $a*a^{-1}\equiv 1\pmod n$，则称 $a^{-1}$为 $a$ 模 $n$ 下的逆。实测欧几里得算法求逆元比较快。

欧拉函数

欧拉函数等于不超过n且和n互素的整数个数,特别的$phi(1)=1$

$phi(i)= n(1-\frac 1{p_1})(1-\frac 1{p_2})...(1-\frac 1{p_k})$其中， $p$ 为 $i$ 的质因数​

若$i$为素数，则$phi(i)=i-1$

int 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)
        ans = ans / n * (n - 1);
}

用筛法计算欧拉函数表

void phi_table(int n)
{
    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);
            }
}

通过素数的倍数依次获得每个数的素因子，再根据公式计算

欧拉定理

欧拉定理：若$a$与$n$互质，则 $a^{phi(n)}\equiv 1\pmod n$

欧拉定理+快速幂求乘法逆元

typedef long long ll;
int pow_mod(ll m, int n, int k) {
    if (n == 0) return 1;
    ll temp, b = 1;
    if (n & 1) b = m;
    temp = pow_mod(m, n >> 1, k);
    return ((temp * temp) % k * b) % k;
}
ll eulerinv(ll a, ll n)
{
    ll t = pow_mod(a, phi(n) - 1, n);
    return t;
}//a与n互质，计算模n下a的逆

离散对数

计算模方程: $a^x\equiv b\pmod n ，n$为素数

1.由欧拉定理，$a^{phi(n)}\equiv 1\pmod n$，故当$x>n-1$时，$a^x$的值就会循环，故只需验证$x=0$到$n-1$的情况

2.可以先计算$a^0,a^1,...,a^m$的情况，然后通过$a^1*a^m,a^2*a^m...,a^m*a^m$计算$a^{m+1}$到$a^{2m}$的情况，以此类推(m取sqrt（n）计算效率较快)

3.判断$a^{1...m}*a^m$是否等于$b$即判断$a^1$到$a^m$中是否存在$b*a^{-m}$

map<int,int> x中，x[e]存放e第一次出现的位置

int log_mod(int a, int b, int n) {
    int m, v, e = 1;
    m = sqrt(n + 0.5);
    v = inv(pow_mod(a, m, n), n);
    map<int, int> x;
    x[1] = 0;
    for (int i = 1;i < m;++i) {
        e = e * a % n;
        if (!x.count(e))
            x[e] = i;
    }
    for (int i = 0;i < m;++i) {
        if (x.count(b))
            return i * m + x[b];
        b = b * v % n;
    }
    return -1;
}