Агуулгыг алгасах

Эйлерийн функц

Эйлерийн функц буюу фи-функц $\phi (n)$ нь 1-ээс $n$ хүртэлх (түүнийг оруулаад) $n$-тэй харилцан анхны бүхэл тоонуудын тоог тоолдог. Хоёр тооны хамгийн их ерөнхий хуваагч нь $1$ бол тэдгээрийг харилцан анхны гэнэ ($1$-г дурын тоотой харилцан анхны гэж үздэг).

Эхний хэдэн эерэг бүхэл тооны $\phi(n)$ утгыг энд үзүүлэв:

$$\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|c|} \hline n & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 & 13 & 14 & 15 & 16 & 17 & 18 & 19 & 20 & 21 \\\\ \hline \phi(n) & 1 & 1 & 2 & 2 & 4 & 2 & 6 & 4 & 6 & 4 & 10 & 4 & 12 & 6 & 8 & 8 & 16 & 6 & 18 & 8 & 12 \\\\ \hline \end{array}$$

Шинж чанарууд

Эйлерийн функцийн дараах шинж чанарууд нь түүнийг дурын тооны хувьд тооцоолоход хангалттай:

  • Хэрэв $p$ анхны тоо бол бүх $1 \le q < p$-ийн хувьд $\gcd(p, q) = 1$. Тиймээс бидэнд:
$$\phi (p) = p - 1.$$
  • Хэрэв $p$ анхны тоо ба $k \ge 1$ бол $1$-ээс $p^k$ хооронд $p$-д хуваагддаг яг $p^k / p$ тоо байна. Эндээс бидэнд:
$$\phi(p^k) = p^k - p^{k-1}.$$

  • Хэрэв $a$ ба $b$ харилцан анхны бол:

    $$\phi(a b) = \phi(a) \cdot \phi(b).$$

    Энэ хамаарлыг харах нь тривиал биш. Энэ нь Хятадын үлдэгдлийн теорем-оос гарна. Хятадын үлдэгдлийн теорем нь $0 \le x < a$ ба $0 \le y < b$ бүрийн хувьд $z \equiv x \pmod{a}$ ба $z \equiv y \pmod{b}$ байх цор ганц $0 \le z < a b$ оршихыг баталгаажуулдаг. $z$ нь $a b$-тэй харилцан анхны байх зайлшгүй бөгөөд хүрэлцээтэй нөхцөл нь $x$ нь $a$-тай, $y$ нь $b$-тэй харилцан анхны байх явдал гэдгийг харуулахад хэцүү биш. Тиймээс $a b$-тэй харилцан анхны бүхэл тооны тоо нь $a$ ба $b$-ийн тоонуудын үржвэртэй тэнцүү болно.

  • Ерөнхийдөө харилцан анхны биш $a$ ба $b$-ийн хувьд $d = \gcd(a, b)$-тэйгээр

    $$\phi(ab) = \phi(a) \cdot \phi(b) \cdot \dfrac{d}{\phi(d)}$$

    тэгшитгэл биелнэ.

Тиймээс эхний гурван шинж чанарыг ашиглан бид $n$-ийн үржигдэхүүнд задаргаагаар ($n$-г анхны үржигдэхүүнүүдийн үржвэр болгон задлах) $\phi(n)$-г тооцоолж болно. Хэрэв $n = {p_1}^{a_1} \cdot {p_2}^{a_2} \cdots {p_k}^{a_k}$ бол, энд $p_i$ нь $n$-ийн анхны үржигдэхүүнүүд,

$$\begin{align} \phi (n) &= \phi ({p_1}^{a_1}) \cdot \phi ({p_2}^{a_2}) \cdots \phi ({p_k}^{a_k}) \\\\ &= \left({p_1}^{a_1} - {p_1}^{a_1 - 1}\right) \cdot \left({p_2}^{a_2} - {p_2}^{a_2 - 1}\right) \cdots \left({p_k}^{a_k} - {p_k}^{a_k - 1}\right) \\\\ &= p_1^{a_1} \cdot \left(1 - \frac{1}{p_1}\right) \cdot p_2^{a_2} \cdot \left(1 - \frac{1}{p_2}\right) \cdots p_k^{a_k} \cdot \left(1 - \frac{1}{p_k}\right) \\\\ &= n \cdot \left(1 - \frac{1}{p_1}\right) \cdot \left(1 - \frac{1}{p_2}\right) \cdots \left(1 - \frac{1}{p_k}\right) \end{align}$$

Implementation

Here is an implementation using factorization in $O(\sqrt{n})$:

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

$1$-ээс $n$ хүртэлх Эйлерийн функц $O(n \log\log{n})$-д

Хэрэв бидэнд $1$-ээс $n$ хүртэлх бүх тооны Эйлерийн функц хэрэгтэй бол бүх $n$ тоог үржигдэхүүнд задлах нь үр ашиггүй. Бид Эратосфены шигшүүр-тэй ижил санааг ашиглаж болно. Энэ нь дээр үзүүлсэн шинж чанарт үндэслэсэн хэвээр байгаа боловч тоо бүрийн анхны үржигдэхүүн бүрийн түр зуурын үр дүнг шинэчлэхийн оронд бид бүх анхны тоог олж, тус бүрийн хувьд тэр анхны тоонд хуваагддаг бүх тооны түр зуурын үр дүнг шинэчилнэ.

Энэ арга нь үндсэндээ Эратосфены шигшүүртэй ижил тул complexity нь мөн ижил байна: $O(n \log \log n)$

void phi_1_to_n(int n) {
    vector<int> phi(n + 1);
    for (int i = 0; i <= n; i++)
        phi[i] = i;

    for (int i = 2; i <= n; i++) {
        if (phi[i] == i) {
            for (int j = i; j <= n; j += i)
                phi[j] -= phi[j] / i;
        }
    }
}

Хэсэгчилсэн шигшүүр ашиглан $L$-ээс $R$ хүртэлх Эйлерийн функцийг олох

Хэрэв бидэнд $L$-ээс $R$ хүртэлх бүх тооны Эйлерийн функц хэрэгтэй бол хэсэгчилсэн шигшүүр-ийн аргыг ашиглаж болно.

Алгоритм эхлээд шугаман шигшүүр ашиглан $\sqrt{R}$ хүртэлх бүх анхны тоог $O(\sqrt{R})$ хугацаа ба санах ойд урьдчилан тооцоолно. Дараа нь $[L, R]$ муж дахь тоо бүрийн хувьд эдгээр анхны тоог давтаж, үржигдэхүүнд задаргаанд суурилсан $\phi$ томьёог хэрэглэнэ. Бид тоо бүрийн задраагүй хэсгийг хянахын тулд үлдэгдлийн массив хадгална. Хэрэв бүх бага анхны тоог боловсруулсны дараа үлдэгдэл 1-ээс их хэвээр байвал энэ нь $\sqrt{R}$-ээс их том анхны үржигдэхүүн байгааг илтгэх бөгөөд үүнийг эцсийн шатанд боловсруулна. Мужийн тооцооллын нийт complexity нь $O((R - L + 1) \log \log R) + \sqrt{R}$ юм.

const long long MAX_RANGE = 1e6 + 6;
vector<long long> primes;
long long phi[MAX_RANGE], rem[MAX_RANGE];

vector<int> linear_sieve(int n) { 
    vector<bool> composite(n + 1, 0);
    vector<int> prime;

    // 0 and 1 are not composite (nor prime)
    composite[0] = composite[1] = 1;

    for(int i = 2; i <= n; i++) {
        if(!composite[i]) prime.push_back(i);
        for(int j = 0; j < prime.size() && i * prime[j] <= n; j++) {
            composite[i * prime[j]] = true;
            if(i % prime[j] == 0) break;
        }
    }
    return prime;
}

// To get the value of phi(x) for L <= x <= R, use phi[x - L].
void segmented_phi(long long L, long long R) { 
    for(long long i = L; i <= R; i++) {
        rem[i - L] = i;
        phi[i - L] = i;
    }

    for(long long i : primes) {
        for(long long j = max(i * i, (L + i - 1) / i * i); j <= R; j += i) {
            phi[j - L] -= phi[j - L] / i;
            while(rem[j - L] % i == 0) rem[j - L] /= i;
        }
    }

    for(long long i = 0; i < R - L + 1; i++) {
        if(rem[i] > 1) phi[i] -= phi[i] / rem[i];
    }
}

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

Энэ сонирхолтой шинж чанарыг Гаусс тогтоосон:

$$ \sum_{d|n} \phi{(d)} = n$$

Энд нийлбэр нь $n$-ийн бүх эерэг хуваагч $d$-ээр авагдана.

Жишээ нь 10-ын хуваагчид нь 1, 2, 5 ба 10. Тиймээс $\phi{(1)} + \phi{(2)} + \phi{(5)} + \phi{(10)} = 1 + 1 + 4 + 4 = 10$.

Хуваагчийн нийлбэрийн шинж чанар ашиглан 1-ээс $n$ хүртэлх Эйлерийн функцийг олох

Хуваагчийн нийлбэрийн шинж чанар нь мөн 1-ээс $n$ хүртэлх бүх тооны Эйлерийн функцийг тооцоолох боломж олгодог. Энэ хэрэгжүүлэлт нь Эратосфены шигшүүрт суурилсан өмнөх хэрэгжүүлэлтээс арай энгийн боловч complexity нь арай муу: $O(n \log n)$

void phi_1_to_n(int n) {
    vector<int> phi(n + 1);
    phi[0] = 0;
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
        phi[i] = i - 1;

    for (int i = 2; i <= n; i++)
        for (int j = 2 * i; j <= n; j += i)
              phi[j] -= phi[i];
}

Эйлерийн теорем дэх хэрэглээ

Эйлерийн функцийн хамгийн алдартай, чухал шинж чанарыг Эйлерийн теорем-оор илэрхийлдэг:

$$a^{\phi(m)} \equiv 1 \pmod m \quad \text{хэрэв } a \text{ ба } m \text{ харилцан анхны бол.}$$

$m$ анхны байх тохиолдолд Эйлерийн теорем нь Фермагийн бага теорем болж хувирна:

$$a^{m - 1} \equiv 1 \pmod m$$

Эйлерийн теорем ба Эйлерийн функц практик хэрэглээнд нэлээд олон тохиолддог, жишээ нь хоёул модулийн үржүүлэлтийн урвуу элементийг тооцоолоход ашиглагддаг.

Шууд үр дагавар болгон бид дараах эквивалентыг мөн авна:

$$a^n \equiv a^{n \bmod \phi(m)} \pmod m$$

Энэ нь маш том $n$-ийн хувьд $x^n \bmod m$-г тооцоолох боломж олгоно, ялангуяа $n$ нь өөр тооцооллын үр дүн байвал, учир нь $n$-г модулиар тооцоолох боломжтой болно.

Бүлгийн онол

$\phi(n)$ нь n модулиар авсан мультипликатив бүлгийн $(\mathbb Z / n\mathbb Z)^\times$ эрэмбэ бөгөөд энэ нь нэгжүүдийн (мультипликатив урвуутай элементүүдийн) бүлэг юм. Мультипликатив урвуутай элементүүд нь яг $n$-тэй харилцан анхны элементүүд байна.

$n$ модулиар авсан $a$ элементийн мультипликатив эрэмбэ-г $\operatorname{ord}_n(a)$ гэж тэмдэглэдэг бөгөөд энэ нь $a^k \equiv 1 \pmod n$ байх хамгийн бага $k>0$ юм. $\operatorname{ord}_n(a)$ нь $a$-гаар үүсгэгдсэн дэд бүлгийн хэмжээ тул Лагранжийн теоремоор дурын $a$-гийн мультипликатив эрэмбэ нь $\phi(n)$-г хуваах ёстой. Хэрэв $a$-гийн мультипликатив эрэмбэ нь боломжит хамгийн их $\phi(n)$ бол $a$ нь анхдагч язгуур бөгөөд бүлэг нь тодорхойлолтоор циклик болно.

Ерөнхийлөл

Сүүлийн эквивалентын бага мэдэгддэг хувилбар байдаг бөгөөд энэ нь харилцан анхны биш $x$ ба $m$-ийн хувьд $x^n \bmod m$-г үр ашигтай тооцоолох боломж олгодог. Дурын $x, m$ ба $n \geq \log_2 m$-ийн хувьд:

$$x^{n}\equiv x^{\phi(m)+[n \bmod \phi(m)]} \mod m$$

Баталгаа:

$p_1, \dots, p_t$ нь $x$ ба $m$-ийн ерөнхий анхны хуваагчид байг, $k_i$ нь $m$ дэх тэдгээрийн зэрэг байг. Тэдгээрийг ашиглан бид $a = p_1^{k_1} \dots p_t^{k_t}$ гэж тодорхойлно, ингэснээр $\frac{m}{a}$ нь $x$-тэй харилцан анхны болно. Мөн $k$ нь $a$ нь $x^k$-г хуваах хамгийн бага тоо байг. $n \ge k$ гэж үзвэл бид дараах байдлаар бичиж болно:

$$\begin{align}x^n \bmod m &= \frac{x^k}{a}ax^{n-k}\bmod m \\ &= \frac{x^k}{a}\left(ax^{n-k}\bmod m\right) \bmod m \\ &= \frac{x^k}{a}\left(ax^{n-k}\bmod a \frac{m}{a}\right) \bmod m \\ &=\frac{x^k}{a} a \left(x^{n-k} \bmod \frac{m}{a}\right)\bmod m \\ &= x^k\left(x^{n-k} \bmod \frac{m}{a}\right)\bmod m \end{align}$$

Гурав ба дөрөв дэх мөрийн хоорондох эквивалент нь $ab \bmod ac = a(b \bmod c)$ гэсэн баримтаас гарна. Үнэндээ хэрэв $r < c$-тэйгээр $b = cd + r$ бол $ar < ac$-тэйгээр $ab = acd + ar$ болно.

$x$ ба $\frac{m}{a}$ харилцан анхны тул бид Эйлерийн теоремыг хэрэглэж, үр ашигтай ($k$ маш бага; үнэндээ $k \le \log_2 m$) томьёог авна:

$$x^n \bmod m = x^k\left(x^{n-k \bmod \phi(\frac{m}{a})} \bmod \frac{m}{a}\right)\bmod m.$$

Энэ томьёог хэрэглэхэд хэцүү боловч бид үүнийг $x^n \bmod m$-ийн зан төлөвийг шинжлэхэд ашиглаж болно. Зэргүүдийн дараалал $(x^1 \bmod m, x^2 \bmod m, x^3 \bmod m, \dots)$ нь эхний $k$ (эсвэл түүнээс бага) элементийн дараа $\phi\left(\frac{m}{a}\right)$ урттай цикл рүү ордгийг харж болно. $\phi\left(\frac{m}{a}\right)$ нь $\phi(m)$-г хуваадаг ($a$ ба $\frac{m}{a}$ харилцан анхны тул $\phi(a) \cdot \phi\left(\frac{m}{a}\right) = \phi(m)$), тиймээс бид үеийн урт нь $\phi(m)$ гэж мөн хэлж болно. Мөн $\phi(m) \ge \log_2 m \ge k$ тул бид хүссэн, хамаагүй энгийн томьёог гаргаж болно:

$$ x^n \equiv x^{\phi(m)} x^{(n - \phi(m)) \bmod \phi(m)} \bmod m \equiv x^{\phi(m)+[n \bmod \phi(m)]} \mod m.$$

Дасгал бодлогууд