//我都二分两个了，怎么一直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 编辑 ]

MAXN是多少？试过吗？

先说说吧，这是个数学题。
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。。。。
还是不用生成素数，直接找？

太崩溃了，又被输出格式符误导了。

下面是我的AC代码。

#include<stdio.h>
int p[4800], pn;
void init()
{
    int i, j;
    char isp[46338] = {0};
    for(i = 2; i < 46338; i++)
    if(!isp[i])
    {
        p[pn++] = i;
        for(j = i + i; j < 46338; j += i) isp[j] = 1;
    }
}
long long s(int n, int ip)
{
    long long a;
    int b, t;
    if(n == 1) return 1;
    for(; ip < pn && n % p[ip]; ip++);
    if(ip >= pn) return n + 1LL;
    t = p[ip];
    for(a = 1, b = t; !(n % t); n /= t, b *= t) a += b;
    return a * s(n, ip);
}
int main()
{
    int n;
    init();
    while(scanf("%d", &n) != EOF) printf("%I64d\n", s(n, 0));
    return 0;
}

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

刚刚有点事离开了一下。呵呵，没注意我的成绩，看来还不错。

将递归展开速度还会更快些，不过代码会更复杂。这样的单递归带来的多余开销很少，所以展不展开没有质的差别。

你的算法思想没有问题，不过在实现中冗余太多，没有很好的利用已经计算过的结果。

还有64位运算比32位运算慢很多，在32位满足的情况下尽量不要做超范围的运算。

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

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

呵呵，希望我的代码不会给你造成太大的困扰。能解这样的题目，你的水平并没有自己说的那么差。