#01.1 - Số học (Ước số, bội số, số nguyên tố)

Cho số nguyên dương \(N (N \leq 2∗10^9)\).

Yêu cầu: Đếm số lượng ước số của \(N\) và tổng các ước số của \(N\).

Input

• Số nguyên dương \(N\)

Output

• Chứa hai số nguyên là sô lượng ước số và tổng các ước của \(N\)

Example

10 

4 18

Cho một số nguyên \(n\) và \(k\) (\(1 \leq n, k \leq 100\)). In ra các bội số của \(k\) trong đoạn từ \(1\) đến \(n\), mỗi số in trên 1 dòng.

Input

• Một dòng chứa số nguyên \(n\).
• Một dòng chứa số nguyên \(k\).

Output

• Các bội số của \(k\) trong đoạn từ \(1\) đến \(n\).

Example

10
3

3
6
9

Trong ngày thực tập đầu tiên, thầy Hải có một câu đố nho nhỏ cho các học sinh của mình. Cho một số nguyên \(n\), hãy kiểm tra \(n\) có phải là số nguyên tố hay không?

Số nguyên tố là số tự nhiên lớn hơn 1 chỉ có hai ước số dương phân biệt là 1 và chính nó.

Input:

• Gồm một dòng duy nhất là số nguyên \(n (|n| \le 10^{12})\)

Output:

• In ra YES nếu \(n\) là số nguyên tố. Ngược lại in ra NO.

Example

9

NO

7

YES

Số nguyên dương \(p\) gọi là ước số chung lớn nhất của \(a\) và \(b\) khi \(a\) và \(b\) cùng chia hết cho \(p\) và \(p\) là lớn nhất.

Viết chương trình nhập vào một số nguyên dương \(a,b\) \((min(a,b) \leq 10^{12})\).

Hãy in ra ước số chung lớn nhất của \(a\) 𝑣à \(b\).

Input

• Nhập \(2\) số nguyên dương \(a,b\).

Output

• In ra ước số chung lớn nhất của chúng.

Example

54 72 

18

Cho số nguyên \(n\). Hãy phân tích \(n\) thành tích các thừa số nguyên tố.

Ví dụ: \(n=36 \rightarrow n=2\times2\times3\times3\). Khi đó có \(2\) thừa số \(2\) và \(2\) thừa số \(3\).

Input

• Vào từ thiết bị nhập chuẩn gồm dòng duy nhất chứa một số nguyên dương \(n\) \((n\le{10}^{14})\).

Output

• Ghi ra thiết bị xuất chuẩn gồm các ước nguyên tố xếp từ nhỏ đến lớn của \(n\) cùng số lần xuất hiện trong cách phân tích đó.

Example

16

2 4

25

5 2

36

2 2
3 2

Bội chung nhỏ nhất của \(2\) số là số nguyên dương nhỏ nhất mà chia hết cho cả hai số đó.

Ký hiệu \(LCM(a,b)\) là bội chung nhỏ nhất của hai số \(a\) và \(b\). \(LCM(a,b,c)\) là bội chung nhỏ nhất của \(a\), \(b\) và \(c\).

Yêu cầu: Cho số \(n(1 \leq n \leq 10^6)\), hãy tìm giá trị lớn nhất bội chung nhỏ nhất của ba số nguyên dương bất kỳ không lớn hơn \(n\).

Input

• \(1\) số nguyên dương \(n \ (1 \leq n \leq 10^6)\).

Output

• \(MAX( LCM(i,j,k) )\) trong đó \((1 \leq i,j,k \leq n)\).

Example

9 

504

Gọi \(\sigma(n)\) là tổng các ước của một số nguyên \(n\). Ví dụ, \(\sigma(12) = 1 + 2 + 3 + 4 + 6 + 12 = 28\).

Nhiệm vụ của bạn là tính tổng \(\sum_{i=1}^n \sigma(i)\) modulo \(10^9 + 7\).

Input

• Một dòng duy nhất chứa số nguyên \(n\)
• \(1 \leq n \leq 10^{12}\)

Output

• In ra \(\sum_{i=1}^n \sigma(i)\) modulo \(10^9 + 7\)

Example

5

21

Minh trong lúc rảnh rỗi đã nghĩ ra một nhiệm vụ cho bản thân để thư giãn một chút. Anh ta chọn hai số nguyên \(A\) và \(B\) rồi tính ước số chung lớn nhất của các số nguyên "A giai thừa" và "B giai thừa". Minh muốn tìm ra \(GCD (A!, B!)\). Ai cũng biết rằng giai thừa của số nguyên \(x\) là tích của tất cả các số nguyên dương nhỏ hơn hoặc bằng \(x\). Như vậy \(x! = 1\times 2\times 3\times ...\times (x - 1)\times x\). Ví dụ \(4! = 1\times 2\times 3\times 4 = 24\).

Yêu cầu: Tìm ước chung lớn nhất của \(A!\) và \(B!\) .

Dữ liệu

• Một dòng chứa hai số nguyên \(A\) và \(B\) (\(1 ≤ A, B < 10^5\)). Mỗi số cách nhau một khoảng trắng.

Kết quả

• Một số nguyên dương là ước số chung lớn nhất của các số nguyên \(A!\) và \(B!\). Do ước chung lớn nhất của \(A!\) và \(B!\) có thể rất lớn nên ghi kết quả chia dư cho \(10^9 + 7\).

Input

4 3

Output

6

Ràng buộc:

• Có 50% test tương ứng 50% số điểm của bài với \(1 ≤ A, B < 10^5\), \(min\ (A, B) ≤ 12\);
• Có 30% test tương ứng 30% số điểm của bài với \(A, B ≤ 100\);
• Có 20% test khác tương ứng với 20% số điểm còn lại của bài với \(A, B < 10^5\).

Nguồn: THTB - Cấp Quận 2021.

Số nguyên tố \(n\) được gọi là số siêu nguyên tố nếu trong biểu diễn thập phân của nó ta bỏ đi một số tùy ý các chữ số tính từ bên trái, giữ lại ít nhất một chữ số và để nguyên thứ tự những chữ số còn lại thì vẫn được biểu diễn thập phân của một số nguyên tố (biểu diễn thập phân này có thể bắt đầu bằng chữ số \(0\)).

Ví dụ: \(167\) là một số siêu nguyên tố vì \(167\), \(67\) và \(7\) đều là các số nguyên tố. \(2003\) cũng là một số siêu nguyên tố. Tuy nhiên \(89\), \(2000\) không phải những số siêu nguyên tố.

Yêu cầu: Hãy kiểm tra xem \(n\) cho trước có phải là siêu nguyên tố.

Input

• Một số nguyên \(n\) \((0 \leq n \leq 10^{12})\).

Output

• In ra YES nếu \(n\) là số siêu nguyên tố, in ra NO nếu ngược lại.

Example

167

YES

2000

NO

Vì biết Nhật rất kém về số nguyên tố nên trong kì thi này của trường Newton, thầy Nam đã ra một bài toán hóc búa như sau: "Cho 2 số nguyên dương \(a, b\). Hãy tìm số lượng các số trong khoảng [\(a, b\)] sao cho số lượng ước của chúng là một số nguyên tố"

Không chỉ dừng lại đó, thầy Nam còn đánh đố Nhật bằng cách không chỉ cho một bộ \(a, b\) mà cho những \(T\) bộ số. Nhật rất cần qua kì thi này nên anh ấy nhờ đến các bạn lập trình chương trình để giải bài toán của thầy Nam.

Input

• Dòng đầu chứa số nguyên dương \(T\) là số bộ test
• \(T\) dòng sau mỗi dòng gồm 2 số nguyên dương \(a, b\)

Output

• \(T\) dòng, dòng thứ \(i\) là kết quả của bộ test thứ \(i\)

Scoring

• Subtask \(1\) (\(20\%\) số điểm): \(1 \leq a,b \leq 200\), \(T \leq 100\)
• Subtask \(2\) (\(20\%\) số điểm): \(1 \leq a,b \leq 2000\), \(T \leq 1000\)
• Subtask \(3\) (\(20\%\) số điểm): \(1 \leq a,b \leq 10^6\), \(T \leq 1000\)
• Subtask \(4\) (\(20\%\) số điểm): \(1 \leq a,b \leq 10^6\), \(T \leq 10^5\)
• Subtask \(5\) (\(20\%\) số điểm): \(10^6 < a,b \leq 10^{12}\), \(T \leq 10^5\) và số lượng ước phải là số nguyên tố lớn hơn \(2\)

Example

5
12 400
412 1000
32 100
1910 3000
1 100    

82
93
17
141
32