Pre TS10 2023 #03 - Tích chính phương
Xem PDF
Nộp bài
Điểm:
1400 (thành phần)
Thời gian:
1.0s
Bộ nhớ:
256M
Input:
SQP.inp
Output:
SQP.out
Tác giả:
Dạng bài
Ngôn ngữ cho phép
C++, NASM, Pascal, pypy3, Python, text
Cho hai số nguyên dương n, k. Đếm số lượng số nguyên 1 \le x \le n và x \times k là số chính phương.
Input, Output và Subtasks
Input: (SQP.inp)
- Dòng đầu gồm một số nguyên dương t chỉ số testcase (1\le t\le 100)
- Sau đó là t dòng, mỗi dòng gồm duy nhất gồm hai số nguyên dương n, k (n, k \le 10^{18}).
Output: (SQP.out)
- Xuất ra t dòng, mỗi dòng gồm duy nhất một số là số lượng số nguyên dương thỏa mãn đề bài.
Subtasks
- Subtask 1 (40\%): t=1,n \le 10^6,k\le 10^{12}.
- Subtask 2 (30\%): k \le 10^{12}.
- Subtask 3 (30\%): Không có giới hạn gì thêm.
Sample
Input (SQP.inp)
1
10 2
Output (SQP.out)
2
Note
- Có 2 \times 2 = 4 và 2 \times 8 = 16 là các số chính phương.
Bình luận