CF615D Multipliers
组合数学
数论
题解
OI
垃圾JSON！！！有空去把/posts.json改成/posts.xml，JSON的转义符太恶心了。以上是吐槽。
题意
给你一个数，输出其所有因数的乘积。这个数以质因子乘积的形式给出。答案膜，
分析
首先肯定要对n质因数分解已经分好了，只用把相同的因子合并一下指数，记做tim[i]，表示第i个质因子的次数。
我们单独考虑每个质因子对答案的贡献，则答案是，即因数在所有因子里的出现次数，显然
相当于
指数很大，用一下指数循环节公式：
但是！等差数列求和公式里面除了个2，而不与2互质，取不了膜！
ZML老师给了我们一个神奇的公式：
可是我并不会证明它，网上也查不到证明。不过就与2互质了嘛，计算过程中膜它，最后再膜就是了。
另外一种做法是直接用前后缀积来算，就可以避免这个除2的问题了(前缀和在指数上，对MOD-1取膜)
代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
| #include <iostream>
#include <algorithm>
#include <cstring>
#include <cstdio>
using namespace std;
typedef long long int64;
const int MAXN = 200010;
const int64 MOD = 1e9+7;
int vcnt[MAXN];
int cnt[MAXN];
int64 prime[MAXN];
template <typename T>
T pow_mod(T a, T b, T MOD) {
T res = 1;
while (b) {
if (b & 1) res = res * a % MOD;
a = a * a % MOD;
b >>= 1;
}
return res;
}
int main(){
int n;
cin >> n;
for(int i = 1;i<=n;i++){
int p;
cin >> p;
vcnt[p]++;
}
int pcnt = 0;
for(int i = 1;i<=200000;i++){
if(vcnt[i] > 0){
cnt[++pcnt] = vcnt[i];
prime[pcnt] = i;
}
}
int64 prod = 1;
for(int i = 1;i<=pcnt;i++){
prod *= (cnt[i] + 1);
prod %= MOD*2 - 2;
}
int64 ans = 1;
for(int i = 1;i<=pcnt;i++){
int64 k = prod * cnt[i] % (MOD*2 - 2) / 2;
ans *= pow_mod(prime[i],k,MOD);
ans %= MOD;
}
cout << ans << endl;
}
|
