首页 > 代码库 > HDU 2421
HDU 2421
由算术基本定理N=p1^e1*p2^e2....ps^es，可知一个素的因子个数为(e1+1)*(e2+1)*...*(es+1)。
而N的一人因子必定也有n=p1^k1*p2^k2。。。。*ps^ks的形式。因子个数形式同上。
而事实上，即是从ei中选取其中一些来充当k1。那么，所有的因子的个数之和必定是(1+2+...e1+1)*(1+2....e2+1)*...其实即是拆开相乘，相当于有各种组合。而
立方是积性的，所以先把(1^3+2^3+....(e1+1)^3)*(1^3+......)*.......
有公式
1^3+2^3+3^3+...+n^3=(1+2+3+...+n)^2
题目可解。
#include <iostream>#include <cstdio>#include <algorithm>#include <cmath>#define LL __int64using namespace std;int pe[1000],np;const LL MOD=10007;int main(){ int a,b; int kase=0; while(scanf("%d%d",&a,&b)!=EOF){ np=0; for(int i=2;i*i<=a;i++){ if(a%i==0){ int c=0; while(a%i==0){ c++; a/=i; } pe[np++]=c*b; } } if(a>1){ pe[np++]=1*b; } LL ans=1; for(int i=0;i<np;i++){ LL tmp=((((LL)2+(LL)pe[i]))*((LL)pe[i]+(LL)1)/2)%MOD; ans=(ans*((tmp*tmp)%MOD))%MOD; } printf("Case %d: %I64d\n",++kase,ans); } return 0;}
HDU 2421
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。