16哈理工新生赛 D 陈月亮的数学题 (数论) Myth丶恋晨 2022-07-14 11:07 94阅读 0赞 ### 题目链接:[点击打开题目链接][Link 1] ### 陈月亮的数学题 Time Limit: 2000 MS Memory Limit: 32768 K Total Submit: 102(27 users) Total Accepted: 46(23 users) Rating: Special Judge: No Description 陈月亮从小就热爱数学,这天老师讲到任何一个正整数N,我们可以很容易的找出N的所有因子,N1,N2,N3…,Nk,称N一共有k个因子(包含1和N本身)。 求出k的值这个问题对于陈月亮来说实在是太简单了,于是她想要求出N所有因子的因子个数(如N1可能包含n1个因子(包含1和N1本身),N2可能包含n2个因子,…,Nk可能包含nk个因子),然后计算出S的值: Input 第一行为一个整数T(T <= 10000),代表测试数据的组数。 接下来T行每行一个正整数N(N < 2 ^ 31)。 Output 对于每组测试数据,输出S的值。 Sample Input 2 6 9 Sample Output 81 36 Source 2016级新生程序设计全国邀请赛 题解: 我们知道可以将一个数N分解成N=pa11∗pa22∗pa33∗…∗pann,其中Pi为素数。这样N的因子个数为(a1\+1)(a2\+1)(a3\+1)…(ak\+1)=∏ki=1(ai\+1)。 所以N的所有因子的因子个数为∏ki=1(1\+2\+3\+…\+ai\+1)=∏ki=1(1\+ai\+1)(ai\+1)2,但这只是S=n1\+n2\+n3\+…\+nk的值。 所以,我们可以从1\+2\+3\+…\+n=(1\+n)n2。 12\+22\+32\+…\+n2=(2\+n)(1\+n)n6 13\+23\+33\+…\+n3=((1\+n)n2)2中得到启示。 所以最终S=n31\+n32\+n33\+…\+n3k的答案为∏ki=1((1\+ai\+1)(ai\+1)2)2 AC代码: //#include<bits/stdc++.h> #include<cstdio> #include<cstring> #include<iostream> #include<cmath> #include<vector> using namespace std; typedef long long ll; const int maxn=65536; int prime[maxn+10]; ll ans =0; int t,n; vector<int>pricount; int len=0; void init() { for(int i=2;i<=maxn;i++) { if(!prime[i]) prime[++prime[0]]=i; for(int j=1;j<=prime[0] && prime[j]<=maxn/i;j++) { prime[prime[j]*i]=1; if(i%prime[j]==0)break; } } } void get_divisor(int n) { for(int i=1;i<=prime[0] && prime[i] *prime[i]<=n;i++) { int cnt=0; while(n % prime[i]==0) { cnt++; n/=prime[i]; } if(cnt) pricount.push_back(cnt); } if(n>1) pricount.push_back(1); } int main() { init(); cin>>t; while(t--) { pricount.clear(); ans=1; cin>>n; get_divisor(n); len=pricount.size(); //for(vector<int>::iterator it= pricount.begin();it!=pricount.end();it++) //cout<<*it<<endl; ll tmp; for(int i=0;i<len;i++) { tmp=(pricount[i]+1) *(pricount[i]+2)/2; ans*=tmp*tmp; } cout<<ans<<endl; } return 0; } [Link 1]: http://acm.hrbust.edu.cn/index.php?m=ProblemSet&a=showProblem&problem_id=2296
还没有评论,来说两句吧...