DeMen contest (Div 2)

ami có 4 số nguyên dương \(a , b , c , d\). Các bạn cần giải phương trình sau \(a * x + b * y + c * z = d\). Đây là phương trình cơ bản có thể giải bằng thuật toán Euclid mở rộng. Để làm bài toán khó hơn, các bạn cần tìm các số \(x, y, z\) là các số nguyên KHÔNG ÂM thoả phương trình trên vào tổng \(x + y + z\) là lớn nhất.

Input

• 1 dòng chứa 4 số nguyên dương \(a , b , c , d\).

Output

• In ra \(1\) dòng là tổng lớn nhất của một nguyên không âm. Nếu không có nghiệm in ra \(-1\)

Scoring

• Subtask \(1\) (\(90\%\) số điểm): \(a , c , b \leq 100, d \leq 1000\), và đáp án \(x + y + z \leq 100\).

• Subtask \(2\) (\(10\%\) số điểm): \(b , c , a \leq 1000, d \leq 1000\), và đáp án \(x + y + z \leq 1000\).

Example

1 2 3 6 

6

Khi thấy mọi người trong team Dế Mèn đang thảo luận sôi nổi để tạo contest cho các bạn giải trí, Monarchuwu đã rất hào hứng và góp vui bằng một bài như sau:

Cho dãy số \(a\) gồm \(n\) số nguyên dương. Hãy tìm số lớn nhất có dạng \(2^k\) thỏa điều kiện có ít nhất 1 số trong dãy \(a\) chia hết cho nó.

Input

• Dòng đầu là số \(n\) là độ dài của dãy số.
• Dòng thứ 2 là \(n\) số nguyên dương của dãy \(a\)

Output

• In ra số lớn nhất có dạng \(2^k\) thỏa yêu cầu là kết quả cần tìm

Constraints

• \(n \leq 2*10^6\)
• \(a_i \leq 10^{18}\)

Scoring

• Subtask \(1\) (\(56.86\%\) số điểm): \(n \leq 2*10^5\).
• Subtask \(2\) (\(43.14\%\) số điểm): Không có ràng buộc gì thêm.

Example

5
1 2 3 4 5 

4

DeMen100ms là 1 con người đang ở tận cùng của sự cô đơn. Và cậu luôn ghét nhìn thấy người khác đi chơi với nhau. Một hôm, leanhduy123 rủ cậu đi ngồi cafe vỉa hè. Vì thấy mọi người ngoài đường đi chơi cùng nhau nên DeMen100ms rất cay cú.

• Ở ngoài đường đang có \(N\) người được đánh số từ \(1\) đến \(N\).
• Người thứ i có điểm hạnh phúc là \(HP[i]\).
• Tổng số điểm hạnh phúc là : tổng của các tích \(HP[i] * HP[j]\) \((1 \leq i < j \leq n)\)

Yêu cầu: In ra tổng số điểm hạnh phúc có thể đạt được từ \(N\) người đó.

Input

• Dòng đầu nhập \(N\) là người trên đường.
• Dòng thứ 2 là \(N\) số điểm hạnh phúc của \(N\) người.

Output

• In ra tổng điểm hạnh phúc của \(N\) người đó, vì kết quả có thể rất lớn nên lấy kết quả modulo cho \(10^9 + 7\)

Constraints

• \(N \leq 5*10^6\)
• \(0 < HP[i] \leq 3*10^4\)

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(N \leq 5*10^3\).
• Subtask \(2\) (\(60\%\) số điểm): Không có ràng buộc gì thêm.

Example

3
1 2 3 

11

Trong bài tập này nhiệm vụ của bạn là tìm số nguyên dương \(x\) tối thiểu và bạn được cung cấp một danh sách tất cả các ước của \(x\), trừ 1 và \(x\). Nếu không thể tìm được \(x\) thỏa mãn danh sách ước thì có thể coi danh sách là mâu thuẫn.

Nói cách khác, gọi \(S(x)\) là tập hợp các ước khác \(1\) và \(x\) của \(x\). Bạn được cho tập \(D\), hãy tìm số \(x\) nhỏ nhất có \(S(x) = D\) là tập đã cho.

Input

• Dòng đầu tiên chứa số \(T\) \((T \leq 25)\) là số lượng truy vấn. Sau đó \(T\) dòng tiếp theo.
• Dòng đầu tiên của mỗi truy vấn chứa số nguyên \(n\) \((n \leq 300)\) là số lượng của danh sách.
• Dòng thứ hai của mỗi truy vấn chứa \(n\) số nguyên \(d_1, d_2, ... d_n\), với \(d_i\) \((d_i \leq 10^6)\) là một trong những ước của số đang đoán và tất cả \(d_i\) là khác biệt. Nói cách khác \(D = \{d_1, d_2, ..., d_n\}\)

Output

• Gồm \(T\) dòng mỗi dòng in ra \(-1\) nếu danh sách là mâu thuẫn, ngược lại in ra \(x\) tối thiểu.

Example

2
8
8 2 12 6 4 24 16 3
2
4 7

48
-1

Có một số vấn đề xảy ra trong phòng tin học. Do đó, người ta đã kiểm tra lại hệ thống dây cáp của phòng học.

Biết rằng:

• Máy chủ luôn kết nối với máy số 1
• Mỗi sợi dây cáp chỉ kết nối giữa hai máy bất kỳ với nhau. Đồng nghĩa, thông tin có thể chuyển qua lại giữa 2 máy này
• Máy chủ có thể gửi thông tin đến các máy khác nếu máy chủ kết nối với máy đó hoặc kết nối trung gian qua 1 số máy khác.

** Quan trọng nhất : Đường dây liên thông khi và chỉ khi máy chủ có thể chuyển thông tin đến tất cả các máy còn lại (Bằng cách trực tiếp hoặc gián tiếp)**

Vì DeMen100ms là học sinh chuyên Tin, người ta đã nhờ anh thiết lập một chương trình trả lời câu hỏi :

• Nếu đường dây liên thông thì có thể cắt tối đa bao nhiêu sợi dây để đảm bảo đường dây liên thông (In ra ký tự “-“ trước đáp án) (\(-0\) cũng là một đáp án có thể xảy ra)
• Ngược lại, thì phải gắn tối thiểu bao nhiêu sợi dây để đảm bảo đường dây liên thông (In ra ký tự “+” trước đáp án)

Các bạn hãy giúp anh làm việc này nhé !

Input

• Dòng đầu là 2 số nguyên dương \(n\) và \(k\) lần lượt là số máy và số dây cáp của phòng học \((n, k \leq 10^6)\)
• \(k\) dòng tiếp theo, dòng thứ \(i\) là \(2\) số nguyên dương \(a_i, b_i\) : Dây cáp thứ \(i\) nối 2 máy \(a_i\) và \(b_i\). \((a_i, b_i \leq n, a_i \neq b_i)\)

Output

• In ra kết quả của câu hỏi trên

Scoring

• Subtask \(1\) (\(30\%\) số điểm): \(n \leq 5, k \leq 10\)
• Subtask \(2\) (\(30\%\) số điểm): \(n, k \leq 10^3\)
• Subtask \(1\) (\(40\%\) số điểm): \(n, k \leq 10^6\)

Example

5 5
1 2
1 3
1 4
1 5
2 3

-1

4 3
1 2
2 3
3 1

1

Sau khi sửa máy tính xong, giờ học lại được tiếp tục. Và thế là các học sinh phải thực hiện những phép tính trên máy tính của mình. Thế nhưng, thật thiếu công bằng khi mỗi máy tính có khả năng tính toán khác nhau.

Máy tính có số hiệu \(a\) có thể thực hiện \(1 + 2 + ... + (a - 1) + a\) phép tính/giây.

Có thể coi phòng học có vô hạn máy tính.

Yêu cầu : Với mỗi truy vấn \([L, R]\), gọi \(f(a)\) là tổng số phép tính/giây của máy có số hiệu \(a\) trong \(K\) giây. Hãy tính \(f(L) + f(L+1) + ... + f(R)\).

Input

• Dòng đầu tiên là \(T\) tương ứng với số truy vấn cần hỏi \((T \leq 5*10^5)\)
• \(T\) dòng tiếp theo, mỗi dòng là \(3\) số nguyên dương \(L, R, K\) tương ứng với truy vấn và thời gian cần hỏi và (\(L, R, K \leq 10^{18}, L \leq R)\)

Output

• In ra \(T\) dòng tương ứng với câu trả lời cho \(T\) truy vấn (Vì số có thể rất lớn nên hãy in kết quả modulo \(10^9+7\))

Scoring

• \(K <= 10^{18}\)
• Subtask \(1\) (\(20\%\) số điểm): \(T = 1; \ L, R \leq 10^5\)
• Subtask \(2\) (\(20\%\) số điểm): \(T = 1; \ L,R \leq 10^{18}, R - L \leq 10^5\)
• Subtask \(3\) (\(20\%\) số điểm): \(T \leq 5*10^5; \ L, R \leq 10^{18}, R - L \leq 10\)
• Subtask \(4\) (\(20\%\) số điểm): \(T = 1; \ L,R \leq 10^{18}\)
• Subtask \(5\) (\(20\%\) số điểm): \(T \leq 5*10^5; \ L, R \leq 10^{18}\)

Example

3
1 2 23
2 4 2
1 4 3

92
38
60