---
tags: VNOJ,
title: Thách Thức Lập Trình Xuân Giáp Thìn - Thử thách Vũ Môn
author: theTai123
---

<style>
.markdown-body { max-width: 2048px; }
</style>

$\Huge \text{🐲 Thách Thức Lập Trình Xuân Giáp Thìn - Thử thách Vũ Môn
}$

-----

###### 🔗 Link: [https://oj.vnoi.info/problem/dovui_2024_a](https://oj.vnoi.info/problem/dovui_2024_a)
###### 📌 Tags: `Math`,`Brute-force`,`Sieve`
###### 👤 Writer: @theTai123
###### 📋 Content:

[TOC]

_____
## Tóm Tắt

Cho một dãy số gồm $n$ số nguyên dương $a_1,a_2,...,a_n$. Với mỗi số nguyên dương $a_i$ đếm xem có bao nhiêu nghiệm nguyên dương thỏa mãn phương trình $x+y+gcd(x,y)=a_i$. $(1\leq n \leq2\cdot10^5,1\leq a_i \leq4\cdot10^6)$.

*Từ đây, gọi $m$ là $\max (a_i$)*.

-----
## Subtask 1

> **Tags:** `Brute-force`
> [color=lightgreen]

Ở subtask này, ta vét cạn tất cả các cặp $(x,y)$ nguyên dương và kiểm tra có thỏa mãn không.

> **Complexity:** $O(n \cdot m^2)$
> [color=lightgreen]

:::success
:::spoiler Code của theTai123

#include <iostream>
#include <algorithm>
#define pb push_back
#define pop pop_back
#define fi first
#define se second
typedef long long ll;
typedef double db;
template<typename A, typename B> bool minimize(A& a, const B& b) {return a > b ? a = b, 1 : 0;}
template<typename A, typename B> bool maximize(A& a, const B& b) {return a < b ? a = b, 1 : 0;}

using namespace std;
int n;
int res;

void process(int x) {
    res = 0;
    for(int i = 1; i < x; i++) {
        for(int j = 1; j < x; j++) {
            if(i + j + __gcd(j, i) == x) res++;
        }
    }
    cout << res << " ";
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int x; cin >> x;
        process(x);
    }
    return 0;
}

:::

------
## Subtask 2

>**Tags:** `Math` `Brute-force`
> [color=lightgreen]

Từ phương trình $x+y+gcd(x,y)=a_i$ ,ta đặt $gcd(x,y)=q$. Vì $x$ và $y$ chia hết cho $q$ nên ta có $x=aq, y=bq$ $(a,b\in\mathbb N^*)$.

Suy ra:
$aq+bq+q=a_i$

$\Leftrightarrow q \cdot (a+b+1)=a_i$

$\Leftrightarrow a+b+1={a_i \over q}$

$\Leftrightarrow a+b={a_i \over q}-1$.

Để $a+b \in \mathbb N^*$ thì ${a_i \over q} -1\in \mathbb N^*$ suy ra $q \in Ư(a_i)$ và $q \neq a_i$.

Nếu $gcd(aq,bq)=q$ thì $gcd(a,b)=1$ vậy $a$ và $b$ là hai số nguyên tố cùng nhau.

Do đó nhiệm vụ của ta là đếm tất cả các cặp $a,b \in \mathbb N^*$ sao cho $a+b={a_i \over q}-1$ với $q \in Ư(a_i), q \neq a_i$ và $gcd(a,b)=1$.

> **Complexity:** $O(n \cdot m \log m)$
> [color=lightgreen]

:::success
:::spoiler Code của theTai123

#include <iostream>
#include <algorithm>
#define pb push_back
#define pop pop_back
#define fi first
#define se second
typedef long long ll;
typedef double db;
template<typename A, typename B> bool minimize(A& a, const B& b) {return a > b ? a = b, 1 : 0;}
template<typename A, typename B> bool maximize(A& a, const B& b) {return a < b ? a = b, 1 : 0;}

using namespace std;
int n;

int get(int t) {
    int res = 0;
    for(int j = 1; j < t; j++) {
        if(__gcd(j, t - j) == 1) {
            res++;
        }
    }
    return res;
}

void process(int x) {
    int res = 0;
    for(int i = 1; i < x; i++) {
        if(x % i == 0) res += get(x / i - 1);
    }
    cout << res << " ";
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int x; cin >> x;
        process(x);
    }
    return 0;
}

:::

------
## Subtask 3

> **Tags:** `Math`
> [color=lightgreen]

Từ subtask 2, gọi ${a_i\over q}-1$ là $u$. Ta thấy có đúng $u-1$ cặp số $a,b$ thõa mãn $a+b=u$.

Với mỗi cặp $a,b$ bất kì, nếu $gcd(a,u)=1$ thì $gcd(a,u-a)=1$ hay $gcd(a,b)=1$. Vậy nên ta chỉ cần đếm tất cả các số nguyên tố cùng nhau với $u$ trong đoạn $[1;u-1]$ và ta có thể dễ dàng đếm được bằng cách sử dụng phi hàm Euler $ϕ$ với độ phức tạp $O(\sqrt m)$.

> **Complexity:** $O(n \cdot m \log \sqrt m)$
> [color=lightgreen]

:::success
:::spoiler Code của theTai123

#include <iostream>
#include <math.h>
#define pb push_back
#define pop pop_back
#define fi first
#define se second
typedef long long ll;
typedef double db;
template<typename A, typename B> bool minimize(A& a, const B& b) {return a > b ? a = b, 1 : 0;}
template<typename A, typename B> bool maximize(A& a, const B& b) {return a < b ? a = b, 1 : 0;}

using namespace std;
int n;

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

void process(int x) {
    int res = 0;
    for(int i = 1; i < x; ++i) {
        if(x % i == 0) res += phi(x / i - 1);
    }
    cout << res << " ";
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    for(int i = 1; i <= n; i++) {
        int x; cin >> x;
        process(x);
    }
    return 0;
}

:::

------
## Subtask 4

> **Tags:** `Math` `Sieve`
> [color=lightgreen]

Tương tự như subtask 3 nhưng thay vào đó ta sẽ sử dùng sàng thay vì phải tính lại kết quả.
Độ phức tạp khi sàng là $O(m \log \log m)$.

Để tăng tốc, thay vì kiểm tra ước từ 1 tới $m$, ta sẽ kiểm tra từ 1 tới $\sqrt m$ và kiểm tra xem $m\over i$ có phải ước của $m$ không.

> **Complexity:** $O(n \cdot \sqrt m + m \log \log m)$
> [color=lightgreen]

:::success
:::spoiler Code của theTai123

#include <iostream>
#include <math.h>
#define pb push_back
#define pop pop_back
#define fi first
#define se second
#define MAXA 4000000
typedef long long ll;
typedef double db;
template<typename A, typename B> bool minimize(A& a, const B& b) {return a > b ? a = b, 1 : 0;}
template<typename A, typename B> bool maximize(A& a, const B& b) {return a < b ? a = b, 1 : 0;}

using namespace std;
int n, res;
int phi[MAXA + 7];

void sieve() {
    for(int i = 1; i <= MAXA + 5; i++) {
        phi[i] = i - 1;
    }
    for(int i = 2; i <= MAXA + 5; i++) {
        if(phi[i] == i - 1) {
            for(int j = i; j <= MAXA + 5; j += i) {
                phi[j] -= phi[j] / i;
            }
        }
    }
}

void process(int x) {
    res = 0;
    for(int i = 1; i * i < x; i++) {
        if(x % i == 0) {
            int u = x / i;
            res += phi[u - 1];
            if(x % u == 0) res += phi[x / u - 1];
        }
    }
    int u = sqrt(x);
    if(u * u == x) res += phi[u - 1];
    cout << res << " ";
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    cin >> n;
    int x;
    sieve();
    for(int i = 1; i <= n; i++) {
        cin >> x;
        process(x);
    }
    return 0;
}

:::