16哈理工新生赛 D 陈月亮的数学题（数论）

Myth丶恋晨 2022-07-14 11:07 93阅读 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