这部分主要讲约数和同余

唯一分解定理的推论

divide01

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
vector<int> fac;

void solve(int n) {
for(int i = 1; i*i <= n; i++) {
if(n % i) continue;
fac.push_back(i);
if(i != n/i) fac.push_back(n/i);
}
}

int main() {
const int n = 100;
solve(n);

for(auto x : fac) printf("%d ", x);
}

把一个数分解成最接近的两个数相乘
实际上,是要找出n\geqslant \sqrt{n}
能够被nn 整除的最小的整数ii
(i,n/i)(i, n/i) 就是答案

1
2
3
4
5
6
7
8
9
10
pair<int, int> crack(int n) {
int i = sqrt(n);
int j = n / i;
while (n % i) {
i++;
j = n / i;
}

return make_pair(i, j);
}

由此可见,一个数约数个数的上界是2n2\sqrt{n}

求1到N每个数的正约数集合——倍数法

对每一个数dd[1,N][1, N] 中以dd 作为约数的数

{d,2d,3d,,n/d}\{d, 2d, 3d, \cdots, \lfloor n/d \rfloor \}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
const int maxn = 1e6 + 10;
const int N = 1e6;
vector<int> fac[maxn];

void solve(int n) {
for(int i = 1; i <= n; i++) {
for(int j = 1; j <= n/i; j++)
fac[i*j].push_back(i);
}

for(int i = 1; i <= n; i++) {
for(auto x : fac[i]) printf("%d ", x);
printf("\n");
}
}

int main() {
solve(N);
}

算法实践

HDU2521
HDU2521

反素数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
const ll inf = 0x3f3f3f3f;
const int maxn = 2*1e9 + 5;
int n;

const int p[] = {0, 2, 3, 5, 7, 11, 13, 17, 19, 23, 29};
int c[11];
ll val0 = inf, cnt0 = 1;

void dfs(ll id, ll val, ll cnt) {
if(id == 11) {
if(cnt > cnt0 || (cnt == cnt0 && val < val0)) {
cnt0 = cnt;
val0 = val;
}
return;
}

ll val2 = val;
_rep(i, 0, c[id-1]) {
if(val2 > n) return;

c[id] = i;
dfs(id+1, val2, cnt*(i+1));
val2 *= p[id];
}
}

void init() {
memset(c, 0, sizeof(c));
c[0] = inf;
}


int main() {
freopen("input.txt", "r", stdin);
cin >> n;
init();
//debug(val0);

dfs(1, 1, 1);
printf("%lld\n", val0);
}

取整函数的性质

Acwing199
Acwing199-01
Acwing199-02

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
ll n, k, ans;
ll l, r;

void init() {
ans = n*k;
}

void solve() {
for(l = 1; l <= n; l = r+1) {
r = k/l == 0 ? n : min(n, k/(k/l));
ans -= (k/l) * (r + l) * (r-l+1) / 2;
}
cout << ans << endl;
}

int main() {
//freopen("input.txt", "r", stdin);
cin >> n >> k;

init();
solve();
}

最大公约数

a,bN,gcd(a,b)lcm(a,b)=ab\forall a, b \in \mathbb{N}, \quad \textbf{gcd}(a, b) \cdot \textbf{lcm}(a, b) = a \cdot b

证明,d=gcd(a,b),a0=a/d,b0=b/dd = \text{gcd}(a, b), a_0 = a/d , b_0 = b/d
gcd(a0,b0)=1,lcm(a0,b0)=a0b0\text{gcd}(a_0, b_0)=1, \quad \text{lcm}(a_0, b _0) = a_0 \cdot b_0

lcm(a,b)=lcm(a0d,b0d)=dlcm(a0,b0)=da0b0\text{lcm}(a, b) = \text{lcm}(a_0\cdot d, b_0 \cdot d) = d \cdot \text{lcm}(a_0, b_0) = d \cdot a_0 \cdot b_0
=ab=a \cdot b

公约数算法

对于a,ba, b 的任意公约数dd
da, dbd  (ab)d|a, \ d|b \Rightarrow d \ | \ (a-b)
d[a,ab],d[b,ab]d|[a, a-b], \quad d|[b, a-b]

a,bN,ab,gcd(a,b)=gcd(a,ab) a,bN,gcd(2a,2b)=2gcd(a,b)\begin{gathered} \forall a, b \in \mathbb{N}, a \geqslant b, \textbf{gcd}(a, b) = \textbf{gcd}(a, a- b) \\ \ \\ \forall a, b \in \mathbb{N}, \textbf{gcd}(2a, 2b) = 2 \cdot \textbf{gcd}(a, b) \end{gathered}

Eucilid算法

a,bN,b0,gcd(a,b)=gcd(b,amodb)\forall a, b \in \mathbb{N}, b \neq 0, \textbf{gcd}(a, b) = \textbf{gcd}(b, a \bmod b)

证明其实也比较简单
a=qb+ra = q\cdot b + r
对于任意公约数ddda,d(qb)d|a, d|(q\cdot b)
d(aqb)dr\Rightarrow d | (a-qb) \Leftrightarrow d | r
dd 也是b,rb, r 的公约数,二者的公约数集合相同

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

算法实践

gcd, lcm\textbf{gcd,} \ \textbf{lcm} 问题中,恒等式

lcm=abgcd\text{lcm} = \frac{a\cdot b}{\text{gcd}}

是非常重要的一个理论依据

其中有一些隐含条件
ab=GL,GLa\cdot b = G \cdot L, \quad G \leqslant L
G[factors of a]G \in [\text{factors of } a]

UVA11889
暴力做法

b=cgcd(a,b)ab = \frac{c \cdot \text{gcd}(a, b)}{a}

aa 的因子从小到大排序
我们可以暴力枚举aa 的因子xx,让b=cx/ab=c\cdot x /a
然后检查ab/gcd(a,b)=c?a \cdot b / \text{gcd}(a, b) = c \quad ?

约数中的集合思想

b=gcd(a,b)c/ab = \text{gcd}(a, b) \cdot c /a
如果gcd(a,b)=1,b=c/a\text{gcd}(a,b) =1, \quad b = c/a 就是答案

如果不呢?那么令b0=c/a,b=b0(p1c1pkck)b0 = c/a, \quad b = b0 * (p_1^{c_1} \cdots p_k^{c_k})

这里有一种 过滤因子 的思想

UVA11889

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

ll A, B, C, ans;

inline ll gcd(ll a, ll b) {
return b ? gcd(b, a % b) : a;
}

void solve() {
bool fl = true;
if(C < A || C % A) {
fl = false;
}

if(!fl) {
printf("NO SOLUTION\n");
return;
}

ll B = C/A, k = 1;
if(gcd(A, B) == 1) {
printf("%lld\n", B);
return;
}

while (gcd(A, B) > 1) {
int d = gcd(A, B);
k *= d;
A /= d;
}

printf("%lld\n", B*k);
}

void init() {
//
}

int main() {
freopen("input.txt", "r", stdin);
int kase;
cin >> kase;

while (kase--) {
scanf("%lld%lld", &A, &C);
init();

solve();
}
}

约数问题中的搜索算法

在约数问题中,常见的策略有 dfs
可以用 dfs 枚举可能的所有因子,存在res[]\textbf{res}[\cdots]

Acwing200
Acwing200

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74

typedef pair<int, int> PII;
const int maxn = 50000 + 10;

inline ll gcd(ll a, ll b) {
return b ? gcd(b, a%b) : a;
}

ll a0, a1, b0, b1;

bool fl[maxn];
vector<int> primes;

void getPrimes(int n) {
memset(fl, 0, sizeof(fl));
primes.clear();
for(int i = 2; i <= n; i++) {
if(fl[i]) continue;
primes.push_back(i);
for(int j = i; j <= n/i; j++) fl[i*j] = true;
}
}

vector<PII> fac;
void prework(ll d) {
for(const auto& p : primes) {
if(d % p == 0) {
int c = 0;
while (d % p == 0) c++, d /= p;
fac.push_back(make_pair(p, c));
}
}
if(d > 1) fac.push_back(make_pair(d, 1));
}

void dfs(ll k, ll x, vector<ll>& div) {
if(k == fac.size()) {
div.push_back(x);
return;
}

for(int i = 0; i <= fac[k].second; i++) {
dfs(k+1, x, div);
x *= fac[k].first;
}
}


void init() {
fac.clear();
}

int main() {
freopen("input.txt", "r", stdin);
getPrimes(maxn);

int kase;
cin >> kase;

while (kase--) {
init();
scanf("%lld%lld%lld%lld", &a0, &a1, &b0, &b1);

prework(b1);
vector<ll> div;
dfs(0, 1, div);

ll ans = 0;
for(auto x : div) {
if(gcd(x, a0) == a1 && gcd(x, b0) * b1 == x * b0) ans++;
}
printf("%lld\n", ans);
}
}