| 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. |
| 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: |
| 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 2 2 100 0 1000 9999 3 0 0 0 |
| Sample Output |
Test 1: 11 Test 2: 2 Test 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 long
using 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;
}