## Vòng Xoắn Ốc Số Nguyên Tố
Các bạn gần như không thể AC bài này với các kiến thức lập trình đã được học, vì hai subtask cuối đòi hỏi các bạn phải làm mấy thứ hơi tà đạo so với khối lượng kiến thức phổ thông.

Vì thế, bạn nào ăn được Subtask 1 của bài này đã là giỏi rồi.

### Hướng giải bài toán
- **Bước 1:** Tìm thứ tự của số nguyên tố $N$. Gọi số thứ tự này là $K$.
- **Bước 2:** Xem thử vị trí thứ $K$ trên chuỗi xoắn ốc nằm ở tọa độ nào?

### Bước 1
$K =$ số lượng số nguyên tố trong khoảng từ $1$ tới $N$.
#### Cách cơ bản nhất

def isPrime(num: int) -> bool:
    for i in range(2, num):
        if i * i > num: break        # chỉ duyệt tới sqrt(num)
        if num % i == 0:
            return False
    return True

K = 0
for i in range(1, N + 1):
    if isPrime(i): K += 1

#### Cách làm tốt hơn
Các bạn sẽ dùng sàng nguyên tố Eratosthenes. Để tìm hiểu rõ hơn cách cài, các bạn có thể tham khảo tài liệu **trang 12 của tài liệu [sau](https://drive.google.com/file/d/1ktO_jrIHx7ZnU_NBiBP-PO5kxM5QJGEp/view?usp=sharing "Chuyên đề số học")**. (nhân tiện các bạn có thể thử đọc hết tất cả mọi thứ trong này rồi cho anh nhận xét nha hihi)

#### Cách làm tốt hơn nữa
tà đạo lắm, mà python cũng không ăn được đâu :(

### Bước 2
**Nhận xét:** hình dạng xoắn ốc theo chu kỳ sau:
- phải 1
- lên 1
- trái 2
- xuống 2
- phải 3
- lên 3
- trái 4
- xuống 4
- ...

Tóm lại là nếu gộp phải-lên-trái-xuống thành một vòng, thì vòng thứ $i$ (đếm từ 1) sẽ có dạng như sau:
- phải $2i-1$
- lên $2i-1$
- trái $2i$
- xuống $2i$

Thực ra vì đằng nào chúng ta cũng chỉ làm tới subtask 1, nên các bạn thấy được quy luật này thì cài nhanh lắm.
Tuy nhiên anh sẽ phân tích tới cuối luôn.

#### Quy ước
- sang phải: `y += 1`
- sang trái: `y -= 1`
- lên trên: `x += 1`
- xuống dưới: `x -= 1`

#### Cách làm đơn giản nhất
Nếu đang di chuyển theo hướng nào, **nếu còn đủ bước**, đi một mạch tới đích luôn. (Ví dụ, đang đi trái 4 thì cho `y -= 4` luôn).
Tuy nhiên, nếu số lượng bước không đủ, thì đi chừng đó bước rồi dừng luôn và in đáp án.

luot = 1
x, y = 0, 0
while K > 0:
    # phải
    if 2 * luot - 1 < K: 
        K -= 2 * luot - 1; y += 2 * luot - 1
    else:
        y += K; break
    
    # trên
    if 2 * luot - 1 < K: 
        K -= 2 * luot - 1; x += 2 * luot - 1
    else:
        x += K; break
    
    # tương tự với trái và xuống
        
    luot += 1            # sang lượt mới

#### Cách cài ngắn hơn
Thay vì gộp 4 chiều vào một vòng và làm 4 cặp if/else, ta duyệt từng chiều một
Công thức sẽ có thay đổi.

# 0123=PLTX
addX = [ 0; +1;  0; -1]
addY = [+1;  0; -1;  0]

luot = 1; 
x, y = 0, 0
while K > 0:
    buoc = (luot + 1) // 2
    if buoc < K:
        x += addX * buoc
        y += addX * buoc
        K -= buoc
    else:
        x += addX * K
        y += addX * K
        break
    
    luot += 1

Hoặc rút gọn hơn là:

# 0123=PLTX
addX = [ 0; +1;  0; -1]
addY = [+1;  0; -1;  0]

luot = 1; 
x, y = 0, 0
while K > 0:
    buoc = (luot + 1) // 2
    if buoc > K: buoc = K        
    # nếu không đủ bước, ở dòng 14 sẽ trừ về 0
    
    x += addX * buoc
    y += addX * buoc
    K -= buoc
    
    luot += 1

Tuy nhiên thời gian chạy không nhanh hơn, vì bản chất thuật toán vẫn vậy.

#### Thuật toán tối ưu
Vòng thứ $i$ di chuyển tổng cộng $8i-2$ bước, vì vậy vòng sau di chuyển nhiều hơn vòng trước $8$ bước. Vẽ thử để tự kiểm chứng.

1. Các bạn thử tìm công thức $f(x) = \sum\limits_{i=1}^{x} 8i-2=$ số bước di chuyển của tổng cộng $x$ vòng đầu tiên.

2. Sau đó các bạn xem thử ta có thể duyệt bao nhiêu vòng nguyên, bằng cách tìm $x$ lớn nhất sao cho $f(x) \le K$, sử dụng thuật toán chặt nhị phân

3. Tiếp theo bạn lấy $K$ trừ cho $f(x), sẽ ra được vòng lẻ. Bước kết thúc của vòng lẻ này có thể là bước sang phải, lên trên, sang trái hoặc xuống dưới

4. Lần lượt thử một trong bốn trường hợp trên như thuật toán trâu

Rõ ràng, thuật toán chạy nhanh hơn, vì ta rút gọn đi rất nhiều vòng chạy.