CF615D Multipliers

10 May 2019 | duanyll | Tags: OI 题解 数论 组合数学

垃圾JSON!!!有空去把/posts.json改成/posts.xml,JSON的转义符太恶心了。以上是吐槽。

题意

给你一个数,输出其所有因数的乘积。这个数以质因子乘积的形式给出。答案膜$10^9+7$,$m \leq 200000, p_i \leq 200000$

分析

首先肯定要对n质因数分解已经分好了,只用把相同的因子合并一下指数,记做tim[i],表示第i个质因子的次数。

我们单独考虑每个质因子对答案的贡献,则答案是$\prod p_i^k_i$,$k_i$即因数$p_i$在所有因子里的出现次数,显然

相当于

指数很大,用一下指数循环节公式:

但是!等差数列求和公式里面除了个2,而$10^9+7-1$不与2互质,取不了膜!

ZML老师给了我们一个神奇的公式:

可是我并不会证明它,网上也查不到证明。不过$2(10^9+7)-2$就与2互质了嘛,计算过程中膜它,最后再膜$1e9+7$就是了。

另外一种做法是直接用前后缀积来算$k_i$,就可以避免这个除2的问题了(前缀和在指数上,对MOD-1取膜)

代码

#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];
//int64 sum1[MAXN];
//int64 sum2[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;
		}
	}
//	sum1[0] = sum1[pcnt+1] = sum2[0] = sum2[pcnt+1] = 1;
//	for(int i = 1;i<=pcnt;i++){
//		sum1[i] = sum1[i-1] * (cnt[i] + 1);
//		sum1[i] %= MOD - 1;
//	}
//	for(int i = pcnt;i>=1;i--){
//		sum2[i] = sum2[i+1] * (cnt[i] + 1);
//		sum2[i] %= MOD - 1;
//	}
	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 = (sum1[i-1] * sum2[i+1]);
//		k %= MOD - 1;
//		k *= cnt[i] * (cnt[i] + 1) / 2;
//		k %= MOD - 1;
		int64 k = prod * cnt[i] % (MOD*2 - 2) / 2;
		ans *= pow_mod(prime[i],k,MOD);
		ans %= MOD;
	}
	cout << ans << endl;
}