过剩数

11560 过剩数

时间限制:2000MS  内存限制:65535K

题型: 编程题   语言: 无限制

Description

对于一个正整数n,设S为n所有不同因子的和,如果有S-2*n>0则说n为过剩数,

现给两个正整数a和b(1<=a<=b<=100000),计算并输出a与b之间(包括a与b)有多少个
过剩数。

输入格式

多cases,最多1000个测试项
每一行两个数a与b,以一个空格分隔
最后一行为两个0

输出格式

对应每一行按题目要求输出一个数,最后一行不用输出

输入样例

1 10
10 100
100 1000
0 0

输出样例

0
22
225
本来也想着一次判断1~100000的数是不是过剩数,然后多次使用,但对每个数都去判断是否是过剩数必然超时,一时没思路,索性去百度:

完全数过剩数的正整数(>1)倍都是过剩数。

如6为完全数,那么 6的倍数都是过剩数。

证明:若x为完全数或过剩数,它的因子之和(除去自身)不小于x,对于nx,x所有因子的n倍都是nx的因子,其和不小于nx,除此之外,nx还有别的因子(如1),所以nx必然是过剩数。

根据上面这条定理效率便会提高很多

下面是代码:

#include <iostream>
#include <cmath>
using namespace std;
typedef long long ll;
const int maxn=100010;
ll a,b,m;

int g[maxn]={0,0,0},s[maxn]={0,0,};
//用数组g[]来标识是否是过剩数,s[n]统计小于等于n的过剩数个数
int is_abundant(ll x)//判断是否是过剩数
{
    int i;
    double temp=sqrt(x);

    ll sum=0;
    if(temp==(int)temp)
       sum+=(int)temp;

    for(i=1;i<temp;i++)
       if(x%i==0)
          sum+=i+x/i;

    if(sum>2*x)
       return 1;
    else
       return 0;
}

int main()
{
    int i,j,num=0;

    for(i=12;i<maxn;i++)
    {
        if(g[i]==1)
            s[i]=++num;
        else if( is_abundant(i) )
        {
            g[i] = 1;
            s[i] = ++num;
            for( j =i + i; j < maxn ; j +=i )  g[j] = 1;
        }
        else
            s [i] = num;
    }

    while( cin>>a>>b && (a||b) )
    {
        if( g[a] )
           cout<<s[b]-s[a]+1<<endl;
        else
           cout<<s[b]-s[a]<<endl;
    }
    return 0;
}

过剩数

上一篇:关于spring


下一篇:UVA 11461 - Square Numbers 数学水题