Ổn định mảng (phiên bản GCD)

Điểm: 6,00 (OI)

Giới hạn thời gian: 4.0s

Giới hạn bộ nhớ: 256M

Đầu vào: stdin

Đầu ra: stdout

Dạng bài

Ngôn ngữ cho phép

Ada, Algol, Assembly, Awk, C, C#, C++, D, Dart, Forth, Fortran, Go, Groovy, Java, Javascript, Kotlin, Lisp, Lua, Nim, ObjC, Pascal, Perl, PHP, Pike, Python, Racket, Ruby, Rust, Scheme, Scratch, Sed, TCL, Typescript, V, Zig

Cho mảng số nguyên dương $a = [a_{0}, a_{1}, \dots, a_{n - 1}]$ (với $n \geq 2$ ).

Trong một bước, mảng $a$ được thay bằng mảng mới $b$ cùng độ dài $n$ , trong đó mỗi phần tử là ước chung lớn nhất (GCD) của hai phần tử kề nhau theo nghĩa vòng tròn:

$b_{i} = gcd (a_{i}, a_{(i + 1) mod n})$

Tức là phần tử kề phải của $a_{n - 1}$ chính là $a_{0}$ . Sau khi tính xong $b$ , ta gán $a : = b$ .

Ví dụ, nếu $a = [16, 24, 10, 5]$ thì $b = [gcd (16, 24), gcd (24, 10), gcd (10, 5), gcd (5, 16)] = [8, 2, 5, 1]$ .

Với mảng $a$ cho trước, hãy tìm số bước nhỏ nhất để tất cả phần tử của $a$ trở nên bằng nhau (tức $a_{0} = a_{1} = \dots = a_{n - 1}$ ). Nếu ngay từ đầu mảng đã có tất cả phần tử bằng nhau thì đáp án là $0$ .

Dữ liệu vào

Dòng đầu chứa số nguyên $t$ ( $1 \leq t \leq 10^{4}$ ) — số bộ test.
Mỗi bộ test gồm hai dòng:
- Dòng đầu chứa $n$ ( $2 \leq n \leq 2 \cdot 10^{5}$ ).
- Dòng thứ hai chứa $n$ số nguyên $a_{0}, a_{1}, \dots, a_{n - 1}$ ( $1 \leq a_{i} \leq 10^{6}$ ).

Tổng giá trị $n$ trên tất cả các bộ test không vượt quá $2 \cdot 10^{5}$ .

Dữ liệu ra

In ra $t$ số — mỗi dòng là đáp án cho một bộ test theo thứ tự đề bài.

Ví dụ

Input	Output	Giải thích
5 4 16 24 10 5 4 42 42 42 42 3 4 6 4 5 1 2 3 4 5 6 9 9 27 9 9 63	3 0 2 1 1	Bộ 1: $[16, 24, 10, 5] \to [8, 2, 5, 1] \to [2, 1, 1, 1] \to [1, 1, 1, 1]$ — cần 3 bước. Bộ 2: đã bằng nhau, 0 bước.
1 5 2 2 2 2 2	0	Toàn bộ phần tử đã bằng nhau từ đầu nên cần 0 bước.

Bình luận

Không có bình luận tại thời điểm này.