一份简单的 NOIP 范围内数论知识初步的总结。

校内交流使用,代码和知识讲解仅供参考。

Slide

Slide : Number Theory

Code

这里是上课可能会用到的代码。

统计约数

1
2
3
4
5
for (int i = 1; i <= sqrt(n); i++)
if (n % i == 0) {
printf("%d\n", i);
if (n / i != i) printf("%d\n", n / i);
}

标准分解

1
2
3
4
5
6
7
8
9
10
11
int lim = sqrt(n);
for (int i = 2; i <= lim; i++)
if (n % i == 0) {
printf("%d ", i);
int cnt = 0;
while (n % i == 0) {
n /= i; ++cnt;
}
printf("%d\n", cnt);
}
if (n != 1) printf("%d 1\n", n);

约数个数

1
2
int ans = 1;
for (int i = 1; i <= n; ++i) ans *= (a[i] + 1);

约数和

1
2
3
4
5
6
7
8
int ans = 1, tmp, nw;
for (int i = 1; i <= n; ++i) {
int nw = 1, sum = p[i];
for (int j = 1; j <= a[i]; ++j) {
nw *= p[i]; sum += nw;
}
ans *= sum;
}

更相减损术

1
2
3
4
5
6
7
8
int stein(int a, int b){
if (a < b) a ^= b, b ^= a,a ^= b;
if (b == 0) return a;
if((!(a & 1)) && (!(b & 1))) return stein(a >> 1, b >> 1) << 1;
else if((a & 1) && (!(b & 1))) return stein(a, b >> 1);
else if((!(a & 1)) && (b & 1)) return stein(a >> 1, b);
else return stein(a - b, b);
}

辗转相除法

递归形式(建议写法)

1
int gcd(int a, int b) { return b ? gcd(b, a % b) : a; }

迭代形式

1
2
3
4
5
6
7
int gcd(int a, int b){  
for(;;) {
if ( b == 0 ) return a;
int temp = a % b;
a = b; b = temp;
}
}

扩展欧几里得

1
2
3
4
void exgcd(int a, int b, int &x, int &y, int &g) {
if (!b){g = a; x = 1; y = 0;}
else { exgcd(b, a % b, y, x, g); y -= a / b * x; }
}

除法分块

1
2
3
4
for(int l = 1, r, t; l <= n; l = r + 1){
t = n / l;
r = (t == 0 ? n : n / t);
}

Eratosthenes 筛法

1
2
3
4
5
6
7
8
9
10
11
int Eratosthenes(int n) {
int p = 0;
is_prime[0] = is_prime[1] = 0;
for (int i = 0; i <= n; ++i) is_prime[i] = 1;
for (int i = 2; i <= n; ++i)
if (is_prime[i]) {
prime[p++] = i;
for (int j = i * i; j <= n; j += i) is_prime[j] = 0;
}
return p;
}

Euler 筛法(筛素数)

1
2
3
4
5
for (int i = 2; i <= n; i++) {
if (!mindiv[i]) prime[++tot] = mindiv[i] = i;
for (int j = 1; j <= tot && prime[j] <= mindiv[i] && (k = prime[j] * i) <= n; j++)
mindiv[k] = prime[j];
}

快速幂

1
2
3
4
5
6
7
8
int fastpow(int a, int k) {
int res = 1;
while (k) {
if (k & 1) res = res * a % p;
a = a * a % p; b >>= 1;
}
return res;
}

线性逆元

1
inv[a] = -(p / a) * inv[p % a];

线性筛欧拉函数

1
2
3
4
5
6
7
phi[1] = 1;
for(int i = 2; i < N; ++i){
if(!phi[i]) prm[++prm[0]] = i,phi[i] = i - 1;
for(int j = 1, k; j <= prm[0] && (k = prm[j] * i) < N; ++j)
if(i % prm[j]) phi[k] = phi[i] * (prm[j] - 1);
else {phi[k] = phi[i] * prm[j]; break;}
}