求因子和

Input

输入一个正整数T(T<=10000),表示有T组数据，每组数据包括一个整数n(1<=n<=1e12)

Output

输出这个数的因子和

Sample Input

1
2

Sample Output

3

解析：

利用唯一分解定理/算数基本定理来解决这道题

因为题目所给的数据十分bigou，所以利用暴力枚举的方式应该是不太现实的

那我们先来解释一下什么是唯一分解定理吧：

对于任何一个整数n，都可以将其拆分为:

$$ n = p_1^{\alpha1}p_2^{\alpha2}p_3^{\alpha3}…p_k^{\alpha k} 其中(p_i)是素数 $$

那么，n的因子个数=

$$ (a_1+1)(a_2+1)(a_3+1)……(a_k+1) $$

n的所有因子和=

$$ (1+p_1^1+p_1^2+p_1^3+…p_1^{a1})(1+p_2^1+p_2^2+p_2^3+…p_2^{a2})…(1+p_k^1+p_k^2+p_k^3+…p_k^{ak}) $$

我们可以利用等比数列求和公式来对式子化简：

$$ (1+p_1^1+p_1^2+p_1^3+…p_1^{a1})={p^{n+1}-1\over p-1} $$

有了这个公式，我们便可以开始写代码了：

#include <bits/stdc++.h>
using namespace std;
const long long MAX=1e6+3;
long long prime[MAX+10],cnt=0,number;
//学长说这里如果不写到1e6+3的话会卡数据999999999989
bool vis[MAX+10];
int getprime(){
    memset(vis,true,sizeof(vis));
    vis[0]=vis[1]=false;
    for (int i=2;i<=MAX;i++){
        if (vis[i])
            prime[++cnt]=i;
        for (int j=1;j<=cnt&&prime[j]*i<=MAX;j++){
            vis[prime[j]*i]=false;
            if (i%prime[j]==0) break;
        }
    }
    return 0;
}
//素数打表
long long sum(long long x){
    long long s=1;
    for (int i=1;prime[i]*prime[i]<=x;i++){
        if (x%prime[i]==0){
            //先找到x的素因子
            long long t=1;
            while (x%prime[i]==0)
                t*=prime[i],x/=prime[i];
            s*=(t*prime[i]-1)/(prime[i]-1);
        }
    }
    if (x>1) s*=(1+x);
    return s;
}
int main(){
    ios::sync_with_stdio(false);
    getprime();
    cin>>number;
    long long n;
    while (number--){
        cin>>n;
        printf("%lld\n",sum(n));
    }
    return 0;
}