Bạn được cho một dãy số nguyên dương $a_1$, $a_2$, $...$, $a_n$. Xét các cặp $(i, j)$ với $1 \le i \le j \le n$, đặt $g$ là ước chung lớn nhất của $a_i$, $a_{i + 1}$, $...$, $a_j$. Hỏi có thể tạo ra bao nhiêu giá trị $g$ khác nhau khi xét tất cả các cặp $(i, j)$.

4
9 6 2 4

6

Bài toán đơn giản mở đầu TLEOJ được phát biểu như sau:
Cho hai con mã và một bàn cờ kích thước $N\times N$, hãy đếm số cách đặt chúng trên bàn cờ sao cho chúng không ở vị trí tấn công nhau.
Bài toán có nhiều truy vấn, với mỗi truy vấn, bạn hãy in ra một dòng thể hiện kết quả.

7
1
2
3
4
5
6
7

0
6
28
96
252
550
1056

Cho một bảng $n$ hàng, $m$ cột. Ô giao giữa hàng $i$ và cột $j$ được kí hiệu là ô $(i,j)$. Ban đầu mỗi ô đều có giá trị bằng $0$. Cho $q$ truy vấn, thuộc một trong ba loại sau:

• $1\, x$: Tăng tất cả các số trong bảng lên $x$ đơn vị ($1\leq x\leq 10^9$)
• $2\, x\, l\, r$: Tăng ô $(x,i)$ lên $(i-l+1)^2$ đơn vị với mọi $l\leq i\leq r$ ($1\leq x\leq n$, $1\leq l\leq r\leq m$)
• $3\, x\, l\, r$: Tăng ô $(i,x)$ lên $(i-l+1)^2$ đơn vị với mọi $l\leq i\leq r$ ($1\leq x\leq m$, $1\leq l\leq r\leq n$)

Yêu cầu: In ra bảng sau tất cả $q$ truy vấn.

3 2 3
2 3 1 2
3 1 2 3
1 2 

2 2
3 2
7 6

Vào một ngày đẹp trời, mèo mẹ mang về cho mèo con $p$ bức tranh $1\times2$ và $q$ bức tranh $2\times1$. Những con mèo con rất thích bức tranh này và chúng quyết định treo hết bức tranh lên tường. Bức tường của nhà mèo có thể biểu diễn dạng một lưới ô vuông $m \times n$ và nếu treo 1 bức tranh có kích thước $a \times b$ thì bức tranh sẽ chiếm $a \times b$ ô trên lưới. Những bức tranh không được phép treo đè lên nhau. Mèo mẹ viết lên ô $(i, j)$ một số nguyên không âm $a_{i, j}$ $(\left| a_{i, j} \right| \le 10^3)$ và đố những con mèo con treo như thế nào để có tổng giá trị $C$ lớn nhất. Giá trị $C$ được tính như sau:

Với bức tranh $1 \times 2$: (có thể lấy hình ở đây)

Với bức tranh $2 \times 1$: (có thể lấy hình ở đây)

Những con mèo con đã ngồi tìm hàng giờ mà vẫn chưa tìm được kết quả. Vì vậy chúng đã nhờ bạn giúp và nếu bạn giúp được bạn sẽ nhận được $1$ con cá :Đ

Test luôn thỏa mãn yêu cầu của đề bài, nghĩa là luôn có cách treo $p$ bức tranh $1\times2$ và $q$ bức tranh $2\times1$ lên bức tường $m \times n$.

3 3 1 1
2 3 1
-1 0 2
2 1 1

5

Có $n$ con mèo sống ở trên một con đường, con mèo thứ $i$ sống ở tọa độ $x_i$. Những con mèo này quyết định, vào mỗi ngày cuối tuần, chúng sẽ gặp nhau ở tọa độ $x$ và kể về những chiến tích của chúng trong tuần qua. Con mèo thứ $i$ cần $\left|x_i-x\right|$ phút để tới được địa điểm gặp mặt, trước đó để đủ năng lượng, con mèo cần phải ngủ $t_i$ phút trước khi đi. Vậy tổng thời gian để con mèo có mặt tại tọa độ $x$ là $t_i+\left|x_i-x\right|$ phút.

Vì những con mèo rất muốn cuộc nói chuyện được bắt đầu nên chúng cần xác định tọa độ $x$ sao cho thời gian để $n$ con mèo gặp nhau là sớm nhất. Nhưng những con mèo này quá lười để tính nên chúng quyết định sẽ hỏi bạn, bạn hãy giúp những con mèo đáng yêu này nhé!

3
1 2 3
4 1 2

1

Cho hai số nguyên dương $a, b$, hãy tính $gcd(a!, b)$ ($a!=1\times 2 \times \dots \times a$, đọc là $a$ giai thừa).

4 36

12

Cho ba số nguyên dương $a, b, n$, hãy tính $gcd(a^n, b)$ ($a^n$ là tích của $n$ số $a$).

2
6 24 2
2 12 5

12
4

Bạn được cho một số nguyên $p$. Ban đầu $p=1$, bạn phải thực hiện $q$ truy vấn, mỗi truy vấn có dạng sau:

• $+$ $w$: tăng số $p$ lên $w$ đơn vị, lưu ý $w$ có thể âm.
• $*$ $w$: nhân số $p$ cho $w$.

Với mỗi truy vấn, bạn cần in ra giá trị $gcd(p, a)$ với $a$ là một số nguyên dương cho trước.

12 5

* 2
+ 1
* 2
* 4
+ -4

2
3
6
12
4

Cho ba số nguyên dương $A, B, M \le 15 \times 10^{18}$. Tính $(A + B) \% M$, với $\%$ là ký hiệu của phép chia lấy dư. (Lưu ý giới hạn thời gian và bộ nhớ bất thường cho bài này)

(Some hint: Kiểu dữ liệu unsigned long long trong C++ có thể lưu trữ số nguyên không âm lên đến $2^{64} - 1$, tương đương khoảng $19*10^{17}$).

Input

• Dòng đầu tiên là số nguyên dương $T \le 5$, số testcases.
• $T$ dòng tiếp theo, mỗi dòng gồm 3 số nguyên dương $A, B, M$.

Output

• Gồm $T$ dòng, mỗi dòng là kết quả của một bài toán theo thứ tự xuất hiện trong input.

Sample

4
1 1 100
2 2 100
4 1 100
5 5 100

2
4
5
10

Một với một là hai
Hai thêm hai là bốn
Bốn với một là năm
Năm với năm là mười
...

Cho một dãy các số nguyên dương $chẵn$ $a_1,a_2,\ldots,a_n$. Đếm số tập hợp $S$ $\subset$ {$1;2;\ldots;n$} sao cho $a_{S_1}\times a_{S_2}\times \ldots \times a_{S_{\left| S \right|}}$ là một $số$ $hoàn$ $hảo$.

Input

• Dòng đầu tiên gồm số nguyên dương $n$ $(n \le 10^6)$.
• Dòng tiếp theo chứa $n$ số nguyên $a_1,a_2,\ldots,a_n$ $(a_i \le 2 \times 10^{18})$.

Output

• Ghi số lượng tập $S$ thỏa mãn. Vì số lượng tập $S$ có thể rất lớn nên chỉ cần in số tập sau khi chia lấy dư cho $10^9+7$.

Constraints

• $20$% số điểm có $n \le 10$ và $a_i \le 10$.
• $20$% số điểm khác có $n \le 10$ và $a_i \le 18$.
• $20$% số điểm khác có $n \le 20$.
• $20$% số điểm khác có $n \le 1000$.
• $20$% số điểm còn lại không có giới hạn gì thêm.

Example

Sample input

4 
2 2 14 6

3

Note

Có $3$ cách chọn sau:

• $a_1 \times a_3 = 2 \times 14 = 28$
• $a_2 \times a_3 = 2 \times 14 = 28$
• $a_4 = 6$

Cho hai xâu $a$ và $b$. Xét một đa tập $S$ gồm tất cả các xâu con liên tiếp khác rỗng của $a$ (mỗi xâu có thể xuất hiện nhiều lần, ví dụ với $a =$ aa thì $S=\{$a, a, aa$\}$) và đa tập $T$ gồm tất cả các xâu con của $b$. Lần lượt so sánh các phần tử của đa tập $S$ và đa tập $T$ và đếm số kết quả (>, <, =) thu được.

Ví dụ với $a=$ab, $b=$ba, ta có $S=\{$a, b, ab$\}$ và $T=\{$b, a, ba$\}$. Dễ thấy có hai phép so sánh trả về kết quả = là a=a và b=b, hai phép so sánh cho kết quả > là ab>a và b>a và 5 phép so sánh cho kết quả <.

Input

• Một dòng duy nhất gồm hai xâu $a$ và $b$ chỉ gồm các chữ cái trong bảng chữ cái tiếng Anh viết thường.

Output

• Một dòng gồm 3 số nguyên dương lần lượt là số phép so sánh trả về kết quả <, kết quả = và kết quả >.

Subtasks: (với $|s|$ là độ dài của xâu $s$, đảm bảo $|a|, |b| \le 10000$)

• $10\%$ số điểm có $|a|, |b| \le 50$.
• $15\%$ số điểm khác có $|a|, |b| \le 100$.
• $15\%$ số điểm khác có $|a|, |b| \le 500$.
• $20\%$ số điểm khác có $|a|, |b| \le 2000$.
• $25\%$ số điểm khác có $|a|, |b| \le 4000$.
• $15\%$ số điểm còn lại không có giới hạn gì thêm.

ab ba

5 2 2

Khi gọi trà sữa, bạn có thể tùy chọn các loại nguyên liệu thêm khác nhau: "có đá / không đá", "có đường / không đường", "có trân châu / không có trân châu", "có pudding / không có pudding", ... Sở thích của khách hàng được biểu diễn bởi chuổi số nhị phân 0 và 1. Ví dụ, nếu cả bốn tùy chọn theo thứ tự nêu trên được sử dụng, thì chuỗi 1100 có nghĩa là "có đá, có đường, không có trân châu, không có bánh pudding".

Minh muốn mua cho $N$ bạn của mình mỗi bạn một cốc trà sữa. Quán có $P$ lựa chọn nguyên liệu. Sau khi mỗi bạn đưa ra sở thích cá nhân của mình, Minh nhận thấy rằng việc mua nhiều loại khác nhau cho mọi người quá phiền phức. Vì vậy Minh định chỉ mua một loại trà sữa cho tất cả. Chắc chắn là bạn bè của Minh sẽ phàn nàn khi thấy mọi sở thích của mình không được đáp ứng. Ví dụ: sở thích của hai bạn lần lượt là 101 và 010, nếu Minh mua 001 thì bạn thứ nhất sẽ phàn nàn một lần, bạn thứ hai sẽ phàn nàn hai lần, tổng cộng sẽ có $3$ lần phàn nàn.

Ngoài ra còn có $M$ loại trà sữa mà cửa hàng không muốn làm vì các nguyên liệu kỵ nhau nên chắc chắn là Minh không thể chọn bất kỳ loại trà sữa nào trong số $M$ loại này (mỗi loại tương ứng với một chuỗi nhị phân).

Yêu cầu: Hãy giúp Minh mua một loại trà sữa duy nhất cho tất cả các bạn sao cho tổng số lượng phàn nàn là ít nhất.

Input

• Dòng đầu tiên ghi duy nhất một số nguyên $T\leq 20$ là số lượng bộ test. Mỗi nhóm dòng trong số $T$ nhóm dòng sau có cấu trúc như sau:
• Dòng thứ nhất gồm ba số nguyên $N$, $M$ và $P$;
• Mỗi dòng trong số $N$ dòng tiếp theo chứa một chuỗi nhị phân (0/1) độ dài $P$ thể hiện yêu cầu của từng bạn;
• Mỗi dòng trong số $M$ dòng tiếp theo chứa một chuỗi nhị phân (0/1) độ dài $P$ chỉ loại trà sữa mà quán không làm.

Output

• Ghi ra $T$ dòng, mỗi dòng ghi tổng số lượng phàn nàn ít nhất tính được của bộ test tương ứng trong input.

Scoring

• Subtask #1: $1 \leq N \leq 10; 1 \leq M \leq \min(10, 2P - 1); 1 \leq P \leq 10$.
• Subtask #2: $1 \leq N \leq 100; 1 \leq M \leq \min(100, 2P - 1);1 \leq P \leq 100$.

1
3 2 3
110
101
000
100
111

4

Lưu ý giới hạn thời gian và bộ nhớ bất thường.

Cho hai số nguyên dương $A$ và $B$, tìm số nguyên dương $C$ sao cho $C^B=A$.

Input

• Gồm 1 dòng duy nhất chứa 2 số $A, B$.

Output

• In ra số $C$ cần tìm.

Constraints

• $C \leq 10^5$, $B \leq 3 \times 10^4$.
• $40\%$ số test có $B, C \le 15$.
• $A$ có không quá $15 \times 10^4$ chữ số.
• Dữ liệu đầu vào đảm bảo luôn tìm được $C$ nguyên dương.

Example

25921 2

161

353393243 3

707

254116810000 4

710

Thành muốn vẽ lên $N$ bức tường liên tiếp nhau. Mỗi bức tường có một giá trị biểu thị độ đẹp nếu được vẽ lên bức tường đó đó. Thế nhưng các bức tường lại bắt đầu bị sụp đổ dần sau những trận lũ lụt gần đây. Vì vậy Thành sẽ vừa vẽ nhanh vừa gia cố bức tường được vẽ đó để nó không bị sụp đổ.

Vào đầu mỗi ngày, Thành sẽ vẽ lên một trong $N$ bức tường. Ngày đầu tiên Thành có thể chọn bất kỳ bức tường nào. Vào các ngày tiếp theo Thành cần vẽ vào bức tường kế tiếp một bức tường đã vẽ. Vào cuối mỗi ngày, một bức tường bị đổ. Bức tường bị đổ luôn là bức tường chưa được vẽ lên và chỉ kề với duy nhất một bức tường khác.

Tổng độ đẹp cuối cùng nhận được là tổng độ đẹp các bức tường mà Thành vẽ lên. Thành mong muốn tìm cách vẽ là dù những bức tường nào bị đổ đi chăng nữa thì tổng độ đẹp cuối cùng tối thiểu là $B$.

Yêu cầu: Hãy giúp Thành tìm được giá trị $B$ lớn nhất có thể.

Input

Dòng đầu tiên ghi duy nhất một số nguyên $T≤5$ là số lượng trường hợp test. Mỗi nhóm dòng trong số $T$ nhóm dòng sau có cấu trúc như sau:

• Dòng thứ nhất gồm một số nguyên: $N$.
• Dòng thứ hai chứa một xâu gồm $N$ chữ số trong khoảng từ 0 đến 9, chữ số thứ $i$ biểu thị độ đẹp của bức tường thứ $i$ nếu được vẽ lên.

Output

• Ghi ra $T$ dòng, mỗi dòng ghi một số nguyên là giá trị $B$ lớn nhất tìm được.

Scoring

• Subtask #1 ($50\%$ số điểm): $2≤N≤100$.
• Subtask #2 ($50\%$ số điểm): $2≤N≤10^6$.

1
3
535

8

Một bữa tiệc có rất nhiều bàn tròn và lớn. Có $n$ vị khách đã đến để dự tiệc, hỏi có bao nhiêu cách sắp xếp chỗ ngồi cho $n$ vị khách này. Hai cách xếp chỗ được coi là khác nhau nếu tồn tại hai người $x$, $y$ mà $x$ ngồi ngay cạnh bên phải của $y$ trong cách xếp này nhưng trong cách kia thì không.

Input

Dòng đầu chứa số tự nhiên $T$ là số lượng test case.

$T$ dòng tiếp theo, mỗi dòng chứa một số tự nhiên $n$.

Output

Ghi $T$ dòng là kết quả tương ứng cho $T$ test case, chỉ cần in ra phần dư khi chia cho $10^9 + 7$.

Scoring

• $T ≤ 10^6, n ≤ 10^6$

• Có $30\%$ số test với $n ≤ 10$

• Có $20\%$ số test với $10 < n ≤ 20$

• Có $20\%$ số test với $20 < n ≤ 1000$

2
1
3

1
6

Một số nguyên dương $x$ được gọi là PRN của $n$ nếu $n$ chia hết cho $x$ và $x + 1$. Ví dụ 6 là PRN của 84 vì 84 chia hết cho 6 và 7. Biết được điều này, thầy PHUND đã cho VanhG số $N$ và đố anh ấy tìm tất cả các số là PRN của $N$.

Input

• Dòng đầu gồm số nguyên dương $T$, là số bộ test ($T \le 20$)
• $T$ dòng tiếp theo, mỗi dòng là một số nguyên dương $N$.

Output

• Với mỗi bộ dữ liệu, in ra kết quả trên mỗi dòng (theo thứ tự các số từ nhỏ đến lớn). Nếu không tồn tại số PRN nào, in ra -1.

Scoring

• Có 50% số điểm: $N \le 10^5$
• Có 10% số điểm: $N \le 10^{10}$
• Có 40% số điểm còn lại: $N \le 10^{18}$

Example

4
35
40
50
60

-1
1 4
1
1 2 3 4 5

Vì kết quả có thể rất lớn nên chỉ cần in kết quả sau khi chia lấy dư cho $10^9+7$.

Cho $n$ đỉnh và các thao tác nối các đỉnh lại với nhau bằng $n - 1$ cạnh có trọng số, sao cho sau khi nối tất cả các cạnh sẽ tạo được một đồ thị liên thông. Trong khi các thao tác nối đỉnh được thực hiện, người ta muốn biết xem liệu có tồn tại đường đi giữa hai đỉnh của đồ thị hay không, và trọng số của đường đi (nếu có) là bao nhiêu. Trọng số của một đường đi giữa hai đỉnh trên cây được định nghĩa là tổng $XOR$ của trọng số của tất cả các cạnh trên đường đi giữa hai đỉnh đó.

5 11
? 1 5 
+ 1 5 3 
+ 5 3 1 
? 1 3 
+ 5 2 6 
? 2 1 
? 2 3 
? 2 4 
+ 1 4 7 
? 2 4 
? 3 4

-1
2 
5 
7 
-1 
2 
5