Хуваагчийн тоо / хуваагчийн нийлбэр¶

Энэ өгүүлэлд бид өгөгдсөн тоо $n$-ийн хуваагчийн тоо $d(n)$ ба хуваагчийн нийлбэр $\sigma(n)$-г хэрхэн тооцоолохыг авч үзнэ.

Хуваагчийн тоо¶

Хуваагч $d$-ийн анхны үржигдэхүүнд задаргаа нь $n$-ийн анхны үржигдэхүүнд задаргааны дэд олонлог байх ёстой нь ойлгомжтой, жишээ нь $6 = 2 \cdot 3$ нь $60 = 2^2 \cdot 3 \cdot 5$-ийн хуваагч юм. Тиймээс бид зөвхөн $n$-ийн анхны үржигдэхүүнд задаргааны бүх өөр дэд олонлогийг олох хэрэгтэй.

Ихэвчлэн $x$ элементтэй олонлогийн дэд олонлогийн тоо $2^x$ байдаг. Гэвч олонлогт давтагдсан элемент байвал энэ нь үнэн байхаа болино. Бидний тохиолдолд зарим анхны үржигдэхүүн $n$-ийн анхны үржигдэхүүнд задаргаанд олон удаа гарч ирж болно.

Хэрэв анхны үржигдэхүүн $p$ нь $n$-ийн анхны үржигдэхүүнд задаргаанд $e$ удаа гарч ирвэл бид дэд олонлогт $p$ үржигдэхүүнийг $e$ хүртэл удаа ашиглаж болно. Энэ нь бидэнд $e+1$ сонголт байна гэсэн үг.

Тиймээс хэрэв $n$-ийн анхны үржигдэхүүнд задаргаа нь $p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$ бол, энд $p_i$ нь ялгаатай анхны тоонууд, хуваагчийн тоо нь:

$$d(n) = (e_1 + 1) \cdot (e_2 + 1) \cdots (e_k + 1)$$

Үүнийг дараах байдлаар бодож болно:

Хэрэв зөвхөн нэг ялгаатай анхны хуваагч $n = p_1^{e_1}$ байвал мэдээж $e_1 + 1$ хуваагч байна ($1, p_1, p_1^2, \dots, p_1^{e_1}$).
Хэрэв хоёр ялгаатай анхны хуваагч $n = p_1^{e_1} \cdot p_2^{e_2}$ байвал бүх хуваагчийг хүснэгт хэлбэрээр байрлуулж болно.

$$\begin{array}{c|ccccc} & 1 & p_2 & p_2^2 & \dots & p_2^{e_2} \\\\\hline 1 & 1 & p_2 & p_2^2 & \dots & p_2^{e_2} \\\\ p_1 & p_1 & p_1 \cdot p_2 & p_1 \cdot p_2^2 & \dots & p_1 \cdot p_2^{e_2} \\\\ p_1^2 & p_1^2 & p_1^2 \cdot p_2 & p_1^2 \cdot p_2^2 & \dots & p_1^2 \cdot p_2^{e_2} \\\\ \vdots & \vdots & \vdots & \vdots & \ddots & \vdots \\\\ p_1^{e_1} & p_1^{e_1} & p_1^{e_1} \cdot p_2 & p_1^{e_1} \cdot p_2^2 & \dots & p_1^{e_1} \cdot p_2^{e_2} \\\\ \end{array}$$

Тиймээс хуваагчийн тоо нь тривиалаар $(e_1 + 1) \cdot (e_2 + 1)$ болно.

Хоёроос олон ялгаатай анхны үржигдэхүүн байвал ижил төстэй үндэслэл гаргаж болно.

long long numberOfDivisors(long long num) {
    long long total = 1;
    for (int i = 2; (long long)i * i <= num; i++) {
        if (num % i == 0) {
            int e = 0;
            do {
                e++;
                num /= i;
            } while (num % i == 0);
            total *= e + 1;
        }
    }
    if (num > 1) {
        total *= 2;
    }
    return total;
}

Хуваагчийн нийлбэр¶

Бид өмнөх хэсгийн ижил үндэслэлийг ашиглаж болно.

Хэрэв зөвхөн нэг ялгаатай анхны хуваагч $n = p_1^{e_1}$ байвал нийлбэр нь:

$$1 + p_1 + p_1^2 + \dots + p_1^{e_1} = \frac{p_1^{e_1 + 1} - 1}{p_1 - 1}$$

Хэрэв хоёр ялгаатай анхны хуваагч $n = p_1^{e_1} \cdot p_2^{e_2}$ байвал бид өмнөхтэй ижил хүснэгт хийж болно. Цорын ганц ялгаа нь одоо бид элементийг тоолохын оронд нийлбэрийг тооцоолохыг хүсэж байна. Хослол бүрийн нийлбэрийг дараах байдлаар илэрхийлж болохыг харахад амархан:

$$\left(1 + p_1 + p_1^2 + \dots + p_1^{e_1}\right) \cdot \left(1 + p_2 + p_2^2 + \dots + p_2^{e_2}\right)$$

$$ = \frac{p_1^{e_1 + 1} - 1}{p_1 - 1} \cdot \frac{p_2^{e_2 + 1} - 1}{p_2 - 1}$$

Ерөнхийдөө $n = p_1^{e_1} \cdot p_2^{e_2} \cdots p_k^{e_k}$-ийн хувьд бид дараах томьёог авна:

$$\sigma(n) = \frac{p_1^{e_1 + 1} - 1}{p_1 - 1} \cdot \frac{p_2^{e_2 + 1} - 1}{p_2 - 1} \cdots \frac{p_k^{e_k + 1} - 1}{p_k - 1}$$

long long SumOfDivisors(long long num) {
    long long total = 1;

    for (int i = 2; (long long)i * i <= num; i++) {
        if (num % i == 0) {
            int e = 0;
            do {
                e++;
                num /= i;
            } while (num % i == 0);

            long long sum = 0, pow = 1;
            do {
                sum += pow;
                pow *= i;
            } while (e-- > 0);
            total *= sum;
        }
    }
    if (num > 1) {
        total *= (1 + num);
    }
    return total;
}

Мультипликатив функцүүд¶

Мультипликатив функц гэдэг нь $a$ ба $b$ харилцан анхны үед

$$f(a \cdot b) = f(a) \cdot f(b)$$

нөхцөлийг хангадаг $f(x)$ функц юм.

$d(n)$ ба $\sigma(n)$ хоёул мультипликатив функц юм.

Мультипликатив функцүүд олон төрлийн сонирхолтой шинж чанартай бөгөөд эдгээр нь тооны онолын бодлогод маш хэрэгтэй байж болно. Жишээ нь хоёр мультипликатив функцийн Дирихлегийн орооцолдуулга нь мөн мультипликатив байна.

Хуваагчийн тоо / хуваагчийн нийлбэр¶