垃圾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; }
|