首页 > 代码库 > 因子和

因子和

2024-07-08 06:33:14   229人阅读

因子和

Accepted : 47 Submit : 289
Time Limit : 4000 MS Memory Limit : 65536 KB

题目描述

如果b能整除a，我们称b为a的因子。现在假设n的所有因子和为f(n)；
给你两个整数a，b，（0 ≤ a ≤ b ≤ 5000000）；
请你求出所有满足a ≤ i ≤ b的f(i)的和；
例如a=1，b=6，那么你就需要计算f(1)+f(2)+f(3)+f(4)+f(5)+f(6)。
我们规定f(0)=0;

输入

不超过2000个样例，每个样例占一行，为两个整数a，b；a=b=0时表示输入结束。

输出

每个样例输出一个整数，占一行。

样例输入

1 1
6 6
1 6
0 0

样例输出

1
12
33

下午做的时候，也是改的素数晒，但是改的不好，依旧超时，没想到把前面的数的因子也储存起来，只储存了自己的因子和
TLE了，看了一下，别人改的，才想明白，自己改的 的确不好
TLE代码：
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <iostream>
#define ll __int64
using namespace std;

ll a[5000001];

int main()
{
    int n,m;
    ll int sum;
    int i=0,j=0;
    a[0] = 0;
    int e = (int)(sqrt(0.0 + 5000000)+1);
    for(i=2;i<=e;i++)
   {

      a[i*i] += i;
      for(j=i+1;i*j<=5000000;j++)
      {
          a[i*j] += i+j;
      }
   }
 while(scanf("%d%d",&n,&m)!=EOF)
 {
     if(n==0 && m== 0)
        break;
     sum = 0;
     for(int i = n;i<=m;i++) <- 这里浪费时间较多，要重新再遍历一次
     {   
         sum+= a[i];
         if(i>1)
            sum += i;
     }
     if(n==0)
     cout<<sum+m-n;
     else
     cout<<sum+m-n+1;
 }
 return 0;
}


AC： 2786Ms

#include <cstdio>
#include <iostream>
#include <cstring>
#include <cstdlib>
#include <cmath>
#define N 5000000
#define ll __int64
using namespace std;
ll a[N+1]={0};
int m,n;
int main()
{
    a[0]=0; a[1]=1;
    for(int i=2; i<=N; i++)
        a[i]=1+i;

    for(int i=2; i<=N; i++) //以i来暴力枚举当前数的所有可能因子
    {
        a[i] += a[i-1];
        //往后覆盖i的2倍的公差为j的元素
        for(int j=i*2; j<=N;j+=i) //<-熟悉吧 ，纯素数筛
            a[j]+=i;
    }

    while(cin>>n>>m)
    {
        if(m==0 && n==0)
            break;
        if(n==0)
            cout<<a[m]<<endl;
        else
            cout<<a[m]-a[n-1]<<endl;
    }
    return 0;
}




联系
我们