LightOj 1098

题目链接：http://lightoj.com/volume_showproblem.php?problem=1098

题意：给你一个数n (0 ≤ n ≤ 2 * 10⁹)，求n以内所有数的因子和，保证结果在LL范围内

我们可以枚举2-sqrt(n)的每个数出现的次数，然后再找到对应因子大于sqrt(n)的数出现数的和;

例如2的倍数4 6 8 10，对应的因子就是2 3 4 5; 时间复杂度为sqrt(n)*T;

#include <stdio.h>
#include <string.h>
#include <algorithm>
#include <math.h>
typedef long long LL;
#define N 1000001
using namespace std;
const double eps = 1e-6;


int main()
{
    int T, t = 1;
    scanf("%d", &T);
    while(T --)
    {
        LL n, ans = 0;
        scanf("%lld", &n);
        LL k = (LL)sqrt(n);
        for(LL i=2; i<=k; i++)
        {
            LL cnt = n/i - 1;///i出现的次数,-1是因为出去i本身;
            ans += cnt*i;///记录和;

            LL p = 2+cnt-1;///p是i因子对应的因子的结束的那个数2,3,4,5,6,...,p;
            if(p <= k) continue;///找到 > k 的因子，求(k+1, k+2, ... ,p)的和，个数为p-k个，根据公式求和；
            ans += (p-k)*(k+1+p)/2;
        }
        printf("Case %d: %lld
", t++, ans);
    }
    return 0;
}