约数篇

· · 个人记录

定义

若整数n除以整数d的余数为0，即d能整除n，则称d为n的约数。记为d|n

●求N的正约数集合

除了完全平方数以外，n的约数都会成对出现。即d|n和n/d|n同时满足。我们再次采用试除法。复杂度O(N)

for(int i = 2; i <= sqrt(n); i++) {
    if(n % i == 0) {
        factor[++m] = i;
        if(n/i != i) factor[++m] = n / i;
    }
}

●求1~N每个数的正约数集合

若把每个数的正约数用试除法求出，复杂度过高。可以反过来考虑，对于每个数d，1-N中以d为约数的数就是d的倍数，d,2d,3d..。

vector<int> factor[N];
for(int i = 1; i <= n; i++) {
    for(int j = 1; j <= n/i; j++) {
        //依然是防爆int的写法
        factor[i*j].push_back(i);
    }
}

●最大公约数

定义

  1. 若d|a且d|b, 则称d为a,b的公约数。使得d最大，则d为a,b的最大公约数。
  2. 若m同时为a和b的倍数，则称m为a,b的公倍数，使得m最小，则m为a, b的最小公倍数。

定理

  1. ∀a,b \in N, a \geq b$， 有 $gcd(a,b) = gcd(b, a-b) = gcd(a, a-b)
  2. ∀a,b \in N$, 有$gcd(2a, 2b) = 2gcd(a,b)
  3. ∀a,b \in N$, $gcd(a,b) * lcm(a,b) = a * b

显然都成立

欧几里得算法

根据第一条，可以得出。

```cpp int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } ``` 另外，根据定理三，我们可以同样迅速的求出lcm。 ## ●互质与欧拉函数 ### 定义 $∀a,b \in N$， 若$gcd(a, b) = 1$ ，则称$a,b$互质。 对于三个数，或更多数的情况，我们把$gcd(a, b, c)$称为$a, b, c$互质。而把$gcd(a,b) = gcd(a,c) = gcd(b,c) = 1$称为$a,b$两两互质。 ### 欧拉函数 1~N中与N互质的数的个数被称为欧拉函数，记为$\phi(N)$。 若在算术基本定理中，$N = p^{c1}_1p^{c2}_2...p^{cm}_m$,则： $\phi(N) = N * \frac {p_1-1} {p_1} * \frac {p_2-1} {p_2}...* \frac {p_m-1} {p_m}

证明可用容斥原理。对于质因子p，1~N中含p的有N \over q个，含质因子q的有N \over p。我们把这两部分去掉，根据容斥原理，我们需要把含有质因子pq的加回来一次。

N - \frac {N} {q} - \frac{N}{p} + \frac{N}{pq} = N(1-\frac{1}{p})(1-\frac{1}{q})

类似的，我们可以对全部质因子进行一次容斥，最后得出式子如上。

根据欧拉函数计算公式，套在质因数分解里就可以了。

int phi(int n) {
    int ans = n;
    for(int i = 2; i <= sqrt(n); i++) {
        if(n % i == 0) {
            ans = ans / i * (i-1);
            while(n % i == 0) n /= i
        }
    }
    if(n > 1) ans = ans / n * (n-1);
    return ans; 
}

性质过多，有点超noip。