# Một ứng dụng khá hay của phi hàm euler

**Người viết** : **Thuỷ Ngọc Quốc** (Trường THPT Chuyên Nguyễn Bỉnh Khiêm)

**Edit :** **Nguyễn Phú Vinh** (THPT Quang Trung)

## Đề bài
Sau khi tốn 3 trang giấy nháp và hàng tỉ lần nộp thì mình đã AC bài này và thấy nó khá hay.

Nay mình sẽ chia sẻ với mọi người về cách giải bài này của mình.

Trước khi vào bài giải bạn có thể đọc qua đề và làm thử ở [đây](https://lqdoj.edu.vn/problem/gcdgcdgcd)

Bài toán này có yêu cầu rất đơn giản:

Cho hai số nguyên dương $X$ và $Y$, hãy đếm số lượng số nguyên $K$ thoả mãn: $gcd(X,Y)=gcd(X+K,Y)$.

## Lời giải

Theo đề ta có: $gcd(X, Y) = gcd(X + K, Y)$
:::info
Ta đặt $gcd(X, Y) = m$ (với m là số nguyên dương)
$\Rightarrow$ $X$ và $Y$ có dạng là $X = am$ và $Y = bm$ (với $a, b$ nguyên dương) và $gcd(a, b) = 1$

:::

Vì $gcd(X, Y) = m = gcd(X + K, Y)$
$\Rightarrow$ $X + K$ , $Y$ có dạng $X + K = cm$ (với $c$ nguyên dương) và $Y = bm$ như đã tính ở trên và $gcd(c, b) = 1$
**Ta có:**
:::info
$X = am$ và $X + K = cm$
$\Leftrightarrow$ $am + K = cm$
$\Leftrightarrow$ $K= (c-a)*m$
:::

Từ đó ta có nhận xét:
:::success
Có thể thấy có bao nhiêu hệ số $c$ thỏa mãn yêu cầu bài toán thì có bấy nhiêu hệ số $K$ cần tìm
:::

$\Longleftrightarrow$ Vậy bây giờ chúng ta cần tìm số lượng số $c$ thỏa mãn điều kiện $0 \le k < y$ và $gcd(c, b) = 1$

:::info

* **Với $k \geq 0$**: $\Leftrightarrow$ $(c-a) \times m \geq 0$ $\Leftrightarrow$ $c >= a$ **(1)**

* **Với K < y**:
$K < y$ $\Leftrightarrow$ $(c-a) \times m \times y$ $\Leftrightarrow$ $c - a < \frac{Y}{m} = b$ $\Leftrightarrow$ $c < b + a$

Hay $c \le b + a - 1$ **(2)**
:::

Từ **(1)** và **(2)** suy ra:

$a \le c \le b + a - 1$ là giới hạn của $c$ thỏa mãn $0 \le k < y$

Bây giờ chúng ta cần tìm thêm $1$ điều kiện nữa là có bao nhiêu hệ số $c$ với $a \le c \le b + a -1$ có $gcd(c, b) = 1$

Ở đây chúng ta có sử dụng **phi hàm euler** để tính với độ phức tạp là $O(\sqrt{n} )$ (bạn có thể tham khảo phi hàm euler bản gốc tại [đây](https://wiki.vnoi.info/translate/he/Number-Theory-4))
:::warning
Nhưng để áp dụng vào bài toán này chúng ta phải biến đổi phi hàm euler lại 1 chút
:::spoiler

int phi(int x, int y)
{
 int ans = x;
 for(int i=2;i<=sqrt(y);i++)
 {
  if (y%i == 0) ans-=ans/i;
  while (y%i == 0)
  {
   y/=i;
  }
 }
 if (y > 1) ans-=ans/y;
 return ans;
}

:::

:::success

Ta sẽ gọi $\phi(X,Y)$ là hàm đếm số lượng số $u$( $1 \le u \le X$) thỏa mãn $gcd(u, Y) = 1$

Vậy đáp áp của bài toán sẽ là: $\phi(b + a - 1, b)$ - $\phi(a-1, b)$ (với $b + a - 1$ và $a-1$ là cận trên và cận dưới của $c$ như đã phân tích ở trên)
:::

**Source code của bài này:**
:::spoiler

int phi(int x, int y)
{
 int ans = x;
 foru(i, 2, sqrt(y))
 {
  if (y%i == 0) ans-=ans/i;
  while (y%i == 0)
  {
   y/=i;
  }
 }
 if (y > 1) ans-=ans/y;
 return ans;
}
void solve(int x, int y)
{
 int m = __gcd(x, y);
 int a = x/m;
 int b = y/m;
 cout << phi(b + a - 1, b) - phi(a-1, b);
 el;
}

:::