數論 - 篩法暴力打表 --- hdu : 12876 Quite Good Numbers

Quite Good Numbers

Time Limit: 1000ms, Special Time Limit:2500ms, Memory Limit:65536KB

Total submit users: 77, Accepted users: 57

Problem 12876 : No special judgement

Problem description

A "perfect" number is an integer that is equal to the sum of its divisors (where 1 is considered a divisor). For example, 6 is perfect because its divisors are 1, 2, and 3, and 1 + 2 + 3 is 6. Similarly, 28 is perfect because it equals 1 + 2 + 4 + 7 + 14.

A "quite good" number is an integer whose

"badness" ? the absolute value of the difference between the sum of its divisors

and the number itself ? is not greater than a specified value. For example, if

the allowable badness is set at 2, there are 11 "quite good" numbers less than

100: 2, 3, 4, 6, 8, 10, 16, 20, 28, 32, and 64. But if the allowable badness is

set at 0 (corresponding to the "perfect" numbers) there are only 2: 6 and

28.

Your task is to write a program to count how many quite good numbers (of

a specified maximum badness) fall in a specified range.

Input

Input will consist of specifications for a series of tests. Information for

each test is a single line containing 3 integers with a single space between

items:

• start (2 <= start < 1000000) specifies the first number to

test

• stop (start <= stop < 1000000) specifies the last number to

• badness (0 <= badness < 1000) specifies the maximum allowable

badness

A line containing 3 zeros terminates the input.

Output

Output should consist of one line for each test comprising the test number

(formatted as shown) followed by a single space and the number of values in the

test range with badness not greater than the allowable

value.

Sample Input

Sample Output

Problem Source

HNU Contest 

Mean:

讓你求從sta到end這個區間中有多少個數滿足：abs(sum-i)<=bad。其中sum是i所有的因子之和，bad是給定的值，代表誤差。

analyse:

由于數字很大，必須打表，我們将10^6次方内i的因子之和求出來。

從篩法求素數得到的啟發，方法很巧妙，具體看代碼。

Time complexity：O(n)

Source code：