首页 > 代码库 > 筛法暴力打表 --- hdu : 12876 Quite Good Numbers

筛法暴力打表 --- hdu : 12876 Quite Good Numbers

2024-07-16 17:09:14   220人阅读

 

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 test
• 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
2 100 22 100 01000 9999 30 0 0
Sample Output
Test 1: 11Test 2: 2Test 3: 6
Problem Source
HNU Contest 

 

Mean:

 

让你求从sta到end这个区间中有多少个数满足：abs(sum-i)<=bad。其中sum是i所有的因子之和，bad是给定的值，代表误差。

 

analyse:

由于数字很大，必须打表，我们将10^6次方内i的因子之和求出来。

从筛法求素数得到的启发，方法很巧妙，具体看代码。

 

Time complexity：O(n)

 

Source code：

 

//Memory   Time// 4988K    40MS// by : Snarl_jsb#include<algorithm>#include<cstdio>#include<cstring>#include<cstdlib>#include<iostream>#include<vector>#include<queue>#include<stack>#include<iomanip>#include<string>#include<climits>#include<cmath>#define MAX 1000005#define LL long longusing namespace std;int sta,stop,bad,ans,kase=1;int sum[MAX];void make_table(){    for(int i=2;i<=MAX;i++)    {        sum[i]++;        for(int j=2;i*j<=MAX;j++) sum[i*j]+=i;    }}int main(){    make_table();    while(scanf("%d %d %d",&sta,&stop,&bad),ans=0,sta+stop+bad)    {        printf("Test %d: ",kase++);        for(int i=sta;i<=stop;i++)        {            if(abs(sum[i]-i)<=bad) ans++;        }        cout<<ans<<endl;    }    return 0;}

　　


联系
我们