ZCMU - 1611: 大四下之回来看看

#include<bits/stdc++.h>
#include<cmath>
#define mem(a,b) memset(a,b,sizeof a);
using namespace std;
typedef long long ll;
int main()
{
    int a[100010]={0};
    a[1]=1;a[2]=4;
    for(int i=3;i<=100000;i++)
    {
        int sum=0,j;
        for(j=1;j<sqrt(i);j++)
            if(i%j==0)
                sum+=(j+i/j)%520623; // 同时加上另外一个因子
        if(j*j==i) sum=(sum+j)%520623; // 最后判断下是否恰好有这种情况
        a[i]=(a[i-1]+sum)%520623;
    }
    int n;
    while(~scanf("%d",&n) && n!=-1)
    {
        for(int i=0;i<n;i++)
        {
            int x,y; scanf("%d%d",&x,&y);
            int ans=a[y]-a[x-1]+520623; // 这里+520623 是因为在预处理的时候，比如：a[2]=4, a[i]=520624 (2<<i) 此时，a[i]==1
            printf("%d\n",ans%520623);
        }
    }
    return 0;
}