2019-04-06-HDOJ-1215

题目：HDOJ1215
已经写过，又采用了一种新的解法。
旧的:打表

#include<stdio.h>

#define N 500001

int p[N]={0};

void euler(void)
{
    int i,j;
    for(i=1;i<N;i++)
        for(j=i+i;j<N;j+=i)
            p[j]+=i;
    return ;
}

int main()
{
    int t,n;
    euler();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        printf("%d\n",p[n]);
    }
    return 0;
}

新的:
依据算术基本定理，n的约数之和=

(p1^0+...+p1^a1)*...*(pn^0+...+pn^an)

PS:在这种数量级下，效率不如打表。

#include<stdio.h>

#define N 50001

int prime[N],to=0;
int factor[N],power[N],cnt;

void isPrime(void)
{
    int i,j;
    char f[N]={'\0'};
    for(i=2,to=0;i<N;i++)
    {
        if(f[i]==0)
            prime[to++] = i;
        for(j=0;j<to && i*prime[j]<N ;j++)
        {
            f[i*prime[j]] = 1;
            if(i%prime[j]==0)
                break;
        }
    }
    return ;
}

void getFactor(int n)
{
    cnt = 0;
    int i;
    for(i=0; i<to && n!=1 ;i++)
    {
        if(n%prime[i]==0)
        {
            factor[cnt++] = prime[i];
            for(power[cnt-1]=0;n%prime[i]==0;power[cnt-1]++)
                n /= prime[i];
        }
    }
    return ;
}

int getSum(void)
{
    int i,j,s;
    for(i=0;i<cnt;i++)
    {
        for(j=0,s=1;j<power[i];j++)
            s = factor[i]*s + 1;
        factor[i] = s;
    }
    for(i=0,s=1;i<cnt;i++)
        s *= factor[i];
    return s;
}

int main(void)
{
    int t,n;
    isPrime();
    scanf("%d",&t);
    while(t--)
    {
        scanf("%d",&n);
        getFactor(n);
        printf("%d\n",getSum()-n);
    }
    return 0;
}