zufe校赛

zufe校赛"/>

zufe校赛

问题 E: E - 简单因子和
时间限制: 1 Sec 内存限制: 256 MB
提交: 111 解决: 7
[提交][状态][讨论版]
题目描述
三水最近遇到了一个数学难题：他知道一个数的因子和是多少，可是n个数相乘起来后得到的新数的因 子和（因子包括1和它本身）为多少呢，请大家帮他解决这个小问题，注意求出来的答案要对1e9 + 7取模

输入
第一行输入一个整数 T，表示接下来有 T 组测试数据

每组测试数据有两行
第一行输入整数n，表示有n个数
第二行输入n个数
• 1 ≤ T ≤ 10.
• 1 ≤ n ≤ 100.
• 1 ≤ a[i] ≤ 1000000.

输出
输出一个数
样例输入
1
5
1 2 3 4 5
样例输出
360

#include<iostream>
#include<cstring>
#include<cstdio>
#include<queue>
#include<cstdlib>
#include<cmath>
#include<map>
#include<algorithm>
using namespace std;
#define ll long long
#define INF 0x3f3f3f3f
#define maxn 1000002
const ll mod = 1e9 + 7;
int n, cnt;
bool prime[maxn];
ll Prime[maxn];
ll a[120], cont[maxn];
void make_prime(){prime[0] = prime[1] = true;for(int i = 2 ; i < maxn ; ++ i){if(!prime[i]){Prime[++cnt] = i;}for(ll j = 1 ; j <= cnt && i * Prime[j] < maxn ; ++ j){prime[i * Prime[j]] = true;if(i % Prime[j] == 0) break;}}
}
ll ksm(ll a, ll b, ll c)
{ll base = a % c, ans = 1;while( b ){if(b & 1)ans = (ans * base) % c;base = (base * base) % c;b >>= 1;}return ans % c;
}
void f(ll p){for(int i = 1 ; Prime[i] <= p ; ++ i){while(p % Prime[i] == 0){p /= Prime[i];cont[Prime[i]] ++;}if(p == 1) break;}
}
int main()
{int t;scanf("%d", &t);make_prime();while(t--){memset(cont, 0, sizeof(cont));memset(a, 0, sizeof(a));scanf("%d", &n);for(int i = 1 ; i <= n ; ++ i){scanf("%lld", &a[i]);f(a[i]);}ll ans = 1;for(int i = 1 ; i < maxn ; ++ i){if(cont[i]){ll x = ksm(i, cont[i] + 1, mod) - 1;ll y = ksm(i - 1, mod - 2, mod);ans = ((ans % mod) * (x * y % mod) ) % mod;}}printf("%lld\n", (ans + mod) % mod);}return 0;
}