Contest Buffalo (Div 2)

Bạn được cung cấp một số nguyên dương \(N\).

Nhiệm vụ của bạn là đếm số lượng số nguyên dương \(x(1 \le x \le N)\) sao cho \(gcd(x,N) = p\).

\(gcd(a,b)\) là ước chung lớn nhất của a và b.

Input

• Gồm hai số nguyên dương \(N\) và \(p\) \((p \le N)\).

Output

• Gồm một số nguyên duy nhất là kết quả của bài toán.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(N \le 1000\).
• Subtask \(2\) (\(50\%\) số điểm): \(N \le 10^6\).

Example

6 2

2

Cho \(1\) số nguyên dương \(n\), đếm xem \(n\) có bao nhiêu ước dương sao cho ước đó có đúng \(4\) ước nguyên dương.

Input

• Một dòng duy nhất là số \(n\).

Output

• \(1\) số duy nhất là kết quả.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 10^4\).
• Subtask \(2\) (\(50\%\) số điểm): \(n \le 10^6\).

Example

8

1

Hôm nay bin9638, vị thần tham lam nhận được một câu đố của vị thần ngu dốt algorit.

algorit cho bin9638 một dãy \(n\) điểm có tọa độ \(x,y\) \((|x|,|y| \le 10^9)\) trên mặt phẳng tọa độ. algorit đố bin9638 với \(n\) điểm trên thì có bao nhiêu cặp đường thẳng vuông góc sao cho mỗi đường thẳng nối \(2\) điểm phân biệt bất kì trong \(n\) điểm trên.

Nếu bin9638 giải ra thì sẽ nhận được một cái nịt siêu to khổng lồ từ algorit, các bạn hãy giúp bin9638 nhé !

Input

• Dòng đầu tiên là số \(n\).
• \(n\) dòng tiếp theo mỗi dòng chứa 2 số nguyên \(x,y\) là tọa độ của điểm tương ứng.

Output

• \(1\) số duy nhất là kết quả.

Scoring

• Subtask \(1\) (\(50\%\) số điểm): \(n \le 10\)
• Subtask \(2\) (\(50\%\) số điểm): \(n \le 1000\)

Example

4
1 0
0 2
0 1
-1 0

2

5
1 0
0 -1
0 1
-1 0
2 0

7

bin9638, em trai Hùng Bá, cũng là một tay định giá thứ thiệt. Khác với anh mình chuyên định giá tiền thì bin9638 lại chuyên định giá những que diêm. Ở nhà của anh có rất nhiều que diêm, từ diêm có gỗ được lấy từ những cây gỗ quý từ rừng rậm Amazon, diêm cổ \(1000\) tuổi, diêm được mạ vàng,....

Một hôm vì thấy định giá diêm mãi cũng chán nên bin9638 nghĩ ra trò mới với những que diêm của mình. bin9638 bắt đầu dùng những que diêm của mình để xếp hình, anh bắt đầu với hình mình thích nhất là hình chữ nhật. Hiện tại bộ sưu tầm diêm của bin9638 có \(n\) que diêm có độ dài \(A_1, A_2, A_3, .... A_n\) \(( 1 \le A_i \le 10^9 )\), anh ấy muốn biết là với bộ sưu tầm này thì có thể chọn ra bao nhiêu bộ \(4\) que diêm để chúng có thể tạo thành hình chữ nhật.

bin9638 cứ xếp mãi vẫn chưa xong, nên bây giờ anh ấy muốn nhờ các bạn chuyên tin giải giúp. Nếu giúp thành công thì còn được bin9638 tặng \(1\) que diêm mạ inox nữa nhé !

Input

• Dòng đầu tiên là số \(n\).
• Dòng tiếp theo là dãy \(A\).

Output

• \(1\) số duy nhất là phần dư của kết quả khi chia cho \(10^9 + 7\).

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(n \le 100\).
• Subtask \(2\) (\(20\%\) số điểm): \(n \le 300\).
• Subtask \(3\) (\(20\%\) số điểm): \(n \le 3000\).
• Subtask \(4\) (\(40\%\) số điểm): \(n \le 2*10^5\).

Example

6
1 2 1 2 1 3

3

bin9638 là một cậu học sinh rất có duyên với số \(4\), cậu có \(4\) người bạn gái, \(4\) năm học sinh giỏi, \(4\) cái máy tính,..... Bởi vậy từ lâu cậu đã coi số \(4\) là con số may mắn của đời mình.

Hôm nay trên lớp bin9638 được thầy giáo toán học algorit giảng bài về ước của các số, vậy nên bin9638 cũng đã nghĩ về một vấn đề toán học liên quan đến con số \(4\) của mình. Cậu tự hỏi nếu có \(1\) dãy số tự nhiên từ \(l\) đến \(r\) thì trong dãy đó có bao nhiêu số tự nhiên có đúng \(4\) ước nguyên dương.

bin9638 vì suy nghĩ bài toán này liên tiếp \(4\) ngày \(4\) đêm đến mất ăn mất ngủ mà vẫn chưa xong. Vì vậy các bạn hãy giúp cậu ấy nhé, nếu làm được thì sẽ được bin9638 tặng một món quà đấy !

Input

• Dòng đầu tiên là số truy vấn \(Q\).
• \(Q\) dòng tiếp theo mỗi dòng là hai số nguyên dương \(l\) và \(r\).

Output

• \(Q\) dòng là kết quả của các truy vấn tương ứng.

Example

1
7 9

1

Scording

• \(30\)% test có \(Q ≤ 10\) và \(l,r ≤ 10^5\).
• \(30\)% test có \(Q ≤ 100\) và \(l,r ≤ 10^7\).
• \(40\)% test có \(Q ≤ 10^5\) và \(l,r ≤ 10^7\).

algorit là một nhà toán học đại tài, người có chỉ số iq cao nhất nhân loại nếu đếm ngược. Đặc biệt anh rất thích thú với những thứ to và nhỏ, các con số không phải là ngoại lệ. Bởi vậy hôm nay algorit đang thắc mắc một bài toán như sau :

Bạn được cung cấp một dãy số gồm \(n\) số nguyên \(A_1,A_2,...,A_n\).

Nhiệm vụ của bạn là đếm số lượng đoạn con có \(max - min = k\). Ở đây \(max\) và \(min\) là giá trị lớn nhất và giá trị nhỏ nhất của đoạn con đó.

algorit suy nghĩ bài toán này đến mức hói cả đầu mà vẫn chưa nghĩ ra, các bạn hãy giúp algorit nhé !

Input

• Dòng đầu tiên gồm 2 số nguyên \(n,k(0 \le k \le 10^9)\).
• Dòng thứ 2 gồm \(n\) số nguyên \(A_1,A_2,A_3,...,A_n(-10^9 \le A_i \le 10^9)\).

Output

• Gồm một số nguyên duy nhất là số lượng đoạn con thỏa mãn.

Scoring

• Subtask \(1\) (\(40\%\) số điểm): \(n \le 10^3\).
• Subtask \(2\) (\(30\%\) số điểm): \(n \le 10^5\).
• Subtask \(3\) (\(30\%\) số điểm): \(n \le 5 \times 10^5\).

Example

5 2
1 2 1 3 3

6