Product

Time Limit: 6000/3000 MS (Java/Others) Memory Limit: 131072/131072 K (Java/Others)

Problem Description

Given a number sequence A1,A2....An,indicating N=∏ni=1iAi.What is the product of all the divisors of N?

Input

There are multiple test cases.
First line of each case contains a single integer n.(1≤n≤105)
Next line contains n integers A1,A2....An,it's guaranteed not all Ai=0.(0≤Ai≤105).
It's guaranteed that ∑n≤500000.

Output

For each test case, please print the answer module 109+7 in a line.

Sample Input

4
0 1 1 0
5
1 2 3 4 5

Sample Output

36
473272463

Source

BestCoder Round #61 (div.2)

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5525

题意：

hdu 5525 Product 数论算贡献

#pragma comment(linker, "/STACK:1024000000,1024000000")

#include<iostream>

#include<cstdio>

#include<cmath>

#include<string>

#include<queue>

#include<algorithm>

#include<stack>

#include<cstring>

#include<vector>

#include<list>

#include<set>

#include<map>

using namespace std;

#define ll long long

#define pi (4*atan(1.0))

#define eps 1e-14

#define bug(x)  cout<<"bug"<<x<<endl;

const int N=2e5+,M=4e6+,inf=;

const ll INF=1e18+,mod=1e9+;

///   数组大小

int prime(int n)

{

    if(n<=)

    return ;

    if(n==)

    return ;

    if(n%==)

    return ;

    int k, upperBound=n/;

    for(k=; k<=upperBound; k+=)

    {

        upperBound=n/k;

        if(n%k==)

            return ;

    }

    return ;

}

vector<int>p;

int si[N];

void init()

{

    for(int i=;i<=;i++)

        if(prime(i))

        p.push_back(i);

}

ll quick(ll a,ll b,ll c)

{

    ll ans=;

    while(b)

    {

        if(b&)ans=(ans*a)%c;

        b>>=;

        a=(a*a)%c;

    }

    return ans;

}

int main()

{

    init();

    int n;

    while(~scanf("%d",&n))

    {

        memset(si,,sizeof(si));

        for(int i=;i<=n;i++)

        {

            int z;

            int x=i;

            scanf("%d",&z);

            for(int j=;j<p.size();j++)

            {

                if(1LL*p[j]*p[j]>x)break;

                if(x==)break;

                while(x%p[j]==)

                {

                    si[j]+=z;

                    si[j]=(si[j])%(*(mod-));

                    x/=p[j];

                }

            }

            if(x!=)

            {

                int pos=lower_bound(p.begin(),p.end(),x)-p.begin();

                si[pos]+=z;

            }

        }

        ll sum=;

        for(int i=;i<p.size();i++)

        {

            sum*=(si[i]+);

            sum%=(*(mod-));

        }

        //cout<<sum<<endl;

        ll ans=;

        for(int i=;i<p.size();i++)

        {

            ans=(ans*quick(p[i],((sum*si[i])%(*(mod-)))/,mod))%(mod);

        }

        printf("%lld\n",ans);

    }

    return ;

}