Số dư

View as PDF

Submit solution

Points: 100.00
Time limit: 1.0s
Memory limit: 1G
Input: stdin
Output: stdout

Author:
Problem type
Allowed languages
C, C++, GAS64, Pascal, Perl, PHP, Python, Sed, TCL, Text

Trong toán học, ước của một số n là các số mn chia hết cho m. Tổng ước số thực sự của một số n là tổng tất cả các số nguyên dương m<nm là ước của n. Trong bài này, ta định nghĩa tổng ước số gần thực sự của một số n là tổng tất cả các số nguyên dương m<nn chia m có số dư không vượt qua một hằng số k cho trước. Cho Q truy vấn, truy vấn thứ i gồm hai số nguyên dương liri, với mỗi truy vấn, hãy tính tổng các tổng ước số gần thực sự của các số trong khoảng từ li tới ri.

Dữ liệu vào

  • Dòng đầu tiên gồm hai số nguyên không âm qk.
  • q dòng tiếp theo, mỗi dòng gồm hai số nguyên dương liri (liri).

Dữ liệu ra

  • Gồm q dòng, dòng thứ i là câu trả lời cho truy vấn thứ i.

Sample input

Copy
2 1
2 5
1 1

Sample output

Copy
17
0

Giải thích

  • Tổng các ước số gần thực sự của các số từ 1 tới 5 lần lượt là 0,1,3,6,7

Giới hạn

  • 20% số test có q,k,li,ri100
  • 20% số test có q106,k,li,ri5000
  • 30% số test có q106,li,ri106,k=0
  • 30% số test có q106,k,li,ri106

Comments

Please read the guidelines before commenting.


There are no comments at the moment.