POJ 3604 Professor Ben 数论

转载请注明出处，谢谢http://blog.csdn.net/ACM_cxlove?viewmode=contents by---cxlove

题意：给出一个N，有若干的因子，求出因子的因子个数立方和。

首先N的范围也是比较大的，求一次因子个数很简单，但是要绕两次显得没有头绪。

将N进行分解，N=p1^a1*p2^a2*……pn^an，则可以得到N有M个因子M=(1+a1)*(1+a2)*(1+a3)……(1+an);

貌似这步在这题中没有用。

对于每个N的因子，只是对于每一个质因子取出若干个bki(0=<bki<=ai)，所有情况列出来

N1=p1^b11*p2^b12……pn^b1n; 对于N1这个因子，因子个数为(1+b11)*(1+b12)*(1+b13)……(1+b1n)

……

……

Nm=p1^bm1*p2^bm2……pn^bmn; 对于N1这个因子，因子个数为(1+bm1)*(1+bm2)*(1+bm3)……(1+bmn)

将所有的立方然后加起来，进行整理

(1^3+2^3+……(1+a1)^3)*(1^3+2^3+……(1+a2)^3)*……(1^3+2^3+……(1+an)^3)

对于N进行因式分解之后，求出a1……an,剩下的就是求立方和。

1^3+2^3……+n^3=(n*n*(n+1)*(n+1))/4;问题解决

#include<iostream>
#include<cstring>
#include<queue>
#include<cstdio>
#include<cmath>
#include<algorithm>
#define N 100005
#define inf  1<<30
#define MOD 9973
#define LL long long
#define eps 1e-7
#define zero(a) fabs(a)<eps
#define equal(a,b) zero(a-b)
using namespace std;
bool flag[10005];
int prime[10005],cnt=0;
int fac[1005],tot;
void Prime(){
	for(int i=2;i<=3000;i++){
		if(flag[i])
			continue;
		prime[cnt++]=i;
		for(int j=2;j*i<=3000;j++)
			flag[i*j]=true;
	}
}
//求1^3+2^3……k^3
LL slove(int k){
	int a=k,b=k+1;
	if(!(a&1))
		a/=2;
	else
		b/=2;
	return (LL)a*a*b*b;
}
int main(){
	int t,n;
	Prime();
	scanf("%d",&t);
	while(t--){
		scanf("%d",&n);
		tot=0;
		for(int i=0;i<cnt&&prime[i]<=n;i++)
			if(n%prime[i]==0){
				fac[tot]=0;
				while(n%prime[i]==0){
					fac[tot]++;
					n/=prime[i];
				}
				tot++;
			}
		if(n>1)
			fac[tot++]=1;
		LL ans=1;
		for(int i=0;i<tot;i++)
			ans*=slove(fac[i]+1);
		printf("%lld\n",ans);
	}
	return 0;
}