给定 $n$ 个正整数 $a_i$,请你输出这些数的乘积的约数之和,答案对 $10^9+7$ 取模。
输入格式
第一行包含整数 $n$。
接下来 $n$ 行,每行包含一个整数 $a_i$。
输出格式
输出一个整数,表示所给正整数的乘积的约数之和,答案需对 $10^9+7$ 取模。
数据范围
$1≤n≤100,$
$1≤a_i≤2×10^9$
输入样例:
3
2
6
8
输出样例:
252
思路
-
由算术基本定理得任意一个数${A = p_1^{k_1 }\times p_2^{k_2 }\times …\times p_n^{k_n}}$则A的约数之和为${(p_1^0 + p_1 ^1 + …+ p_1^{k_1}) \times (p_2^0 + p_2 ^1 + … + p_2^{k_2}) \times … \times (p_n^0 + p_n ^1 + … + p_n^{k_n})}$,展开可以得到${(k_1+1)(k_2+1)…(k_n+1)}$个数之和,也就是$A$的约数之和。
-
下面的问题是如何求${S(n) = x^0 + x^1 + x^2 +…+ x^n}$,${S(n) = 1 + x \times (x^0 + x^1 + … + x^{n-1}) = 1 + S(n-1) \times x}$,边界情况${S(0) = 1}$,所以可以令${t = 1}$,乘以x再加上1得到${S(1)}$,再乘以x并加上1得到${S(2)}$,执行$n$次循环得到${S(n)}$。
AC代码
#include <iostream>
#include <unordered_map>
using namespace std;
typedef long long ll;
const int mod = 1e9 + 7;
unordered_map<int, int> primes;
int main()
{
int n, x;
cin >> n;
while (n --)
{
cin >> x;
for (int i = 2; i <= x / i; i ++)
while (x % i == 0)
{
primes[i] ++;
x /= i;
}
if (x > 1) primes[x] ++;
}
ll res = 1;
for (auto p : primes)
{
ll a = p.first, b = p.second;
ll t = 1;
while (b --) t = (t * a + 1) % mod;
res = res * t % mod;
}
cout << res;
return 0;
}
奇怪的码风又增加了(指时打空格时不打)
/doge
打顺手了,现在又改了改
舒服了(doge
次方上下标怎么往出打啊?搜了半天搜不见.
你可以查一下latex
万分感谢
tql,这个推到公式一出来上大学的我是个麻瓜,只要提出来一个x就找到sn与sn-1的关系,我是菜狗
牛蛙~
$11111$
$真不戳 ~~$