hdu 1215(因子和)

七夕节

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 40119    Accepted Submission(s): 12613

Problem Description

七夕节那天,月老来到数字王国,他在城门上贴了一张告示,并且和数字王国的人们说:"你们想知道你们的另一半是谁吗?那就按照告示上的方法去找吧!"
人们纷纷来到告示前,都想知道谁才是自己的另一半.告示如下:

数字N的因子就是所有比N小又能被N整除的所有正整数,如12的因子有1,2,3,4,6.
你想知道你的另一半吗?

 

Input

输入数据的第一行是一个数字T(1<=T<=500000),它表明测试数据的组数.然后是T组测试数据,每组测试数据只有一个数字N(1<=N<=500000).

 

Output

对于每组测试数据,请输出一个代表输入数据N的另一半的编号.

 

Sample Input

3
2
10
20

 

Sample Output

1
8
22

n的因子和为s(n) 令g(p, e) = (p^(e+1) - 1) / (p-1)，则s(n) = g(p1, e1) * g(p2, e2) * ... * g(pk, ek)

要分类讨论一下。

#include <stdio.h>

#include <algorithm>

#include <string.h>

#include <math.h>

#include <queue>

using namespace std;

typedef long long LL;

const int N = ;

struct Node{

    int p,num;

}node[N];

LL g(int p,int e){ ///g(p, e) = (p^(e+1) - 1) / (p-1)

    LL sum = ;

    for(int i=;i<e+;i++){

        sum*=p;

    }

    sum--;

    return sum/(p-);

}

int main()

{

    int tcase;

    scanf("%d",&tcase);

    while(tcase--){

        int n;

        scanf("%d",&n);

        if(n==){

            printf("0\n");

            continue;

        }

        int m = n;

        int id = ;

        for(int i=;i*i<=n;i++){

            if(n%i==){

                node[id].p = i;

                node[id].num = ;

                while(n%i==) {

                    n/=i;

                    node[id].num++;

                }

                id++;

            }

        }

        if(n>&&m!=n) {node[id].p =n,node[id++].num=;}

        LL sum = ;

        for(int i=;i<id;i++){

            sum*=g(node[i].p,node[i].num);

        }

        if(id==) printf("%d\n",sum);

        else printf("%d\n",sum-m);

    }

    return ;

}