HDU 5525：Product 欧拉定理

Product

 Accepts: 21

 Submissions: 171

 Time Limit: 6000/3000 MS (Java/Others)

 Memory Limit: 131072/131072 K (Java/Others)

问题描述

给n个数{A}_{1},{A}_{2}....{A}_{n}A​1​​,A​2​​....A​n​​，表示N=\prod_{i=1}^{n}{i}^{{A}_{i}}N=∏​i=1​n​​i​A​i​​​​。求N所有约数之积。

输入描述

输入有多组数据.

每组数据第一行包含一个整数n.(1\leq n\leq {10}^{5})(1≤n≤10​5​​)

第二行n个整数{A}_{1},{A}_{2}....{A}_{n}A​1​​,A​2​​....A​n​​,保证不全为0.(0\leq {A}_{i}\leq {10}^{5})(0≤A​i​​≤10​5​​).

数据保证 \sum n\leq 500000∑n≤500000.

输出描述

对于每组数据输出一行为答案对{10}^{9}+710​9​​+7取模的值.

输入样例

4

0 1 1 0

5

1 2 3 4 5

输出样例

36

473272463

官方题解：

做了一道div1的第三题，很好的一道题

参考了别人的代码，其中一处是(p^index)%mod，如果index很大的话，根据欧拉定理，就可以变成(p^(index%(phi(mod))))%mod。记录一下。

代码：

#pragma warning(disable:4996)

#include <iostream>

#include <algorithm>

#include <cmath>

#include <vector>

#include <string>

#include <cstring>

using namespace std;

typedef long long ll;

ll N;

const int maxn = 100010;

const ll mod = 1e9 + 7;

const ll mod2 = 2 * (mod - 1);

ll index[maxn], L[maxn], R[maxn];

int num, pri[maxn], vis[maxn];

vector<int>have[maxn];

void init()

{

	num = 0;

	int i, j, n;

	for (i = 2; i < maxn; i++)

	{

		if (vis[i])

			continue;

		pri[++num] = i;

		for (j = i + i; j < maxn; j = j + i)

		{

			vis[j] = 1;

		}

	}

	for (i = 1; i < maxn; i++)

	{

		n = i;

		for (j = 1; j <= num&&pri[j] <= n; j++)

		{

			while (n%pri[j] == 0)

			{

				have[i].push_back(j);//记录所含有的质数，用质数的下标记录

				n /= pri[j];

			}

		}

	}

}

ll getresult(ll A, ll n, ll k)

{

	ll b = 1;

	while (n > 0)

	{

		if (n & 1)

		{

			b = (b*A) % k;

		}

		n = n >> 1;

		A = (A*A) % k;

	}

	return b;

}

void solve(int cishu, int n)

{

	int temp;

	int si = have[cishu].size();

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

	{

		temp = have[cishu][i];

		index[temp] = (index[temp] + n) % mod2;

	}

}

int main()

{

	//freopen("i.txt", "r", stdin);

	//freopen("o.txt", "w", stdout);

	int x;

	ll k, n, ans;

	init();

	while (scanf("%d", &N) == 1)

	{

		memset(index, 0, sizeof(index));

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

		{

			scanf("%d", &x);

			solve(i, x);

		}

		int p = 1;

		while (pri[p] < N)

			p++;

		N = p;

		L[0] = R[N + 1] = 1;

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

			L[i] = L[i - 1] * (index[i] + 1) % mod2;

		for (int i = N; i >= 1; i--)

			R[i] = R[i + 1] * (index[i] + 1) % mod2;

		ans = 1;

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

		{

			k = L[i - 1] * R[i + 1] % mod2;

			n = index[i] * (index[i] + 1) / 2 % mod2;

			ans = ans*getresult(pri[i], n*k%mod2,mod) % mod;

		}

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

	}

	//system("pause");

	return 0;

}