Bài 4: Tổng ước chẵn - Tài liệu Tin học

Đăng bởi Admin

Tháng 10 9, 2022

https://chuyenhalong.ucode.vn/problems/tong-uoc-chan-118344

Cho số nguyên dương $n$ , ước nguyên dương của $n$ là số $i=1,2, \ldots, n$ thỏa mãn: $n$ chia hết cho $i$ .
Yêu cầu: Hãy lập trình đếm số các số nguyên dương trong đoạn $[L, R]$ có tổng các ước là một số chẵn.

Đầu vào
– Dòng đầu ghi số nguyên dương $q\left(1 \leq q \leq 10^6\right)$ ;
– $q$ dòng tiếp theo mỗi dòng ghi hai số nguyên $L, R\left(1 \leq L \leq R \leq 10^6\right)$

Đầu ra
– Ghi ra $q$ dòng, mỗi dòng ghi ra số lượng số nguyên dương trong đoạn $[L, R]$ thỏa mãn có tổng các ước là một số chẵn.

Ràng buộc
– Sub 1: có $25 \%$ số test của bài ứng với $25 \%$ số điểm của bài có $q=1, n \leq 1000$ ;
– Sub 2: có $25 \%$ số test của bài ứng với $25 \%$ số điểm của bài có $q, n \leq 1000$ ;
– Sub 3: có $25 \%$ số test của bài ứng với $25 \%$ số điểm của bài có $n \leq 5000$ ;
– Sub 4: có $25 \%$ số test của bài ứng với $25 \%$ số điểm của bài có $q, n \leq 10^6$ .