poj-3604(数论+推导)

淩亂°似流年 2022-06-09 06:17 136阅读 0赞

问题描述:

Professor Ben is an old stubborn man teaching mathematics in a university. He likes to puzzle his students with perplexing (sometimes boring) problems. Today his task is: for a given integer N, a1,a2, ... ,an are the factors of N, let bi be the number of factors of ai, your job is to find the sum of cubes of all bi. Looking at the confused faces of his students, Prof. Ben explains it with a satisfied smile:

Let's assume N = 4. Then it has three factors 1, 2, and 4. Their numbers of factors are 1, 2 and 3 respectively. So the sum is 1 plus 8 plus 27 which equals 36. So 36 is the answer for N = 4.

Given an integer N, your task is to find the answer.

Input

The first line contains the number the test cases, Q(1 ≤ Q ≤ 500000). Each test case contains an integer N(1 ≤ N ≤ 5000000)

Output

For each test case output the answer in a separate line.

Sample Input

1
    4

Sample Output

题目题意:题目给我们一个数N,让我们求出这个数的因子的因子数的立方和.

题目分析:这道题目给大家附上一篇大神的博客[点击打开链接][Link 1],能力太弱了，没办法推出这样的公式.

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstring>
    #define ll long long
    using namespace std;
    
    const int maxn=5000000+10;
    int prime[maxn],cnt;
    bool vis[maxn];
    
    void get_prime()//素数打表
    {
        memset (vis,true,sizeof (vis));
        vis[1]=false;
        for (int i=2;i<maxn;i++) {
            if (vis[i]) prime[cnt++]=i;
            for (int j=0;j<cnt&&i*prime[j]<maxn;j++) {
                vis[i*prime[j]]=false;
                if (i%prime[j]==0) break;
            }
        }
    }
    
    int factor[1000][2],fcnt;
    void get_factor(int n)//质因子分解
    {
        memset (factor,0,sizeof (factor));
        fcnt=0;
        for (int i=0;i<cnt&&prime[i]*prime[i]<=n;i++) {
            if (n%prime[i]==0) {
                factor[fcnt][0]=prime[i];
                while (n%prime[i]==0) {
                    factor[fcnt][1]++;
                    n=n/prime[i];
                }
                fcnt++;
            }
        }
        if (n!=1) {
            factor[fcnt][0]=n;
            factor[fcnt++][1]=1;
        }
    }
    int main()
    {
        get_prime();
        int t;
        scanf("%d",&t);
        while (t--) {
            int n;
            scanf("%d",&n);
            get_factor(n);
            ll sum=1;
            for (int i=0;i<fcnt;i++) {
                int res=factor[i][1];
                sum*=pow((res+1)*(res+2)/2,2);
            }
            printf("%lld\n",sum);
        }
        return 0;
    }

[Link 1]: http://blog.csdn.net/famousdt/article/details/7285382