//我都二分两个了，怎么一直T呢

http://218.194.91.48/acmhome/problemdetail.do?&method=showdetail&id=1322  


#include<iostream>
#include<cstdio>
#include<cstring>
#include<cmath>
using namespace std;

typedef __int64 LL;
const int MAXN=1<<16;
int k=0;
LL pri[MAXN],cnt[MAXN],prime[MAXN],flag[MAXN];

void fun()
{
    int i,j;
    for(i=2;i<MAXN;++i){
        if(!flag[i]){
            for(j=i*2;j<MAXN;j+=i)
                flag[j]=1;
        }
    }
    for(i=2;i<MAXN;++i)
        if(!flag[i])    prime[k++]=i;  
}

LL pow(LL a,LL b)
{
    LL tmp=1;
    while(b>0){
        if(b&1)    tmp*=a;
        b>>=1,a*=a;
    }
    return tmp;
}

LL mul(LL a,LL b)
{
    LL tmp=0;
    while(b>0){
        if(b&1)    tmp+=a;
        a+=a,b>>=1;
    }
    return tmp;
}

LL sum(LL p,LL n)
{
    LL tmp=pow(p,n+1);
    return (tmp-1)/(p-1);
}

int main()
{
    fun();
    LL i,n,t=0;
    while(~scanf("%I64d",&n)){
        memset(pri,0,sizeof(pri));
        memset(cnt,0,sizeof(cnt));
        for(i=0;i<k;++i){
            if(n%prime[i]==0){
                pri[t]=prime[i];
                while(n%prime[i]==0){
                    cnt[t]++;
                    n/=prime[i];
                }
                t++;
            }
        }
        LL count=1;
        for(i=0;i<t;++i)
            count=mul(count,sum(pri[i],cnt[i]));  
       printf("%I64d\n",count);
    }
    return 0;
}

[ 本帖最后由 cb_1212 于 2012-7-12 10:55 编辑 ]

先说说吧，这是个数学题。
n的因子之和：（1+p1^1+p1^2+p1^3+…+p1^a1)*(1+p2^1+p2^2+…p2^a2)*(……）p1 p2是n的因子，a1 a2分别是因子个数。

任一整数都可以表示为：p1^a1*p2^a2*…（p1 p2都是素数），是这样的吧？

所以我先生成了素数，然后分别找到整数n的素数因子及其个数，然后带入上面的公式。中间计算p^n和（）*（）*…时用了二分…

不知道是不是n太大的缘故，一直T。是不是我写矬了？

[ 本帖最后由 cb_1212 于 2012-7-12 11:20 编辑 ]

因为n的范围是0<n<2^31。。。额，这个范围内的素数有多少啊？我百度都没百度到。。。
所以瞎开了个1<<16。。。貌似fun()可以生成10^6范围的素数啊……

只能生成10^6范围的素数…n太大了所以不能用生成素数的方法么？…
我都怀疑TLE后还有WA。。。。
还是不用生成素数，直接找？

我刚刚看到了，一看时间和代码长度就知道，太强了…

嗯，谢谢杨大哥指点，受教了！
本人菜鸟啊，水到不行…
你的代码风格我一时还缓不过神。。。

我还是自己又改了下，现在对了…