Prime Number

Created by LXC on Mon May 8 00:14:52 2023

https://codeforces.com/problemset/problem/359/C

ranting: 1900

tag: math, number theory

题意

给出一个数组$a_1, a_2, \cdots, a_n$，以及一个质数x

求$\frac{1}{x^{a_1}}+\frac{1}{x^{a_2}}+\cdots+\frac{1}{x^{a_n}}=\frac{p}{q}$中p和q的最大共因数

这个数很大，最后答案模1e9+7

题解

通分后$\frac{\sum x^{s-a_i}}{x^s}, s= \sum a_i$

看似我们只需要找到最小的$x^{s-a_i}$作为最大公因数，但是如果这个数出现了多次，合并同类项后系数又出现了x，这个时候就产生了新的一项$x^{s-a_i+1}$

所以我们的算法流程就是：
预处理出所有$s-a_i$。
然后不断的找最小值v，并统计v的出现次数c
如果c是x的倍数那么就需要和并生成c/x项v+1
如果c不是x的倍数虽然可以合并生成v+1，但是仍然存在v，所以我们的最小值仍然是v，答案也就找到了，为$x^v$。

代码

#include <bits/stdc++.h>
#define SINGLE_INPUT
#define ll long long
#define N 500005
#define MOD 1000000007
using namespace std;

ll fpow(ll x, ll y) {
    ll rt = 1;
    while (y) {
        if (y & 1) {
            rt = rt * x % MOD;
        }
        x = x * x % MOD;
        y >>= 1;
    }
    return rt;
}

void sol() {
    ll n, x;
    cin >> n >> x;
    vector<ll> a(n);
    ll s = 0;
    for (ll& i : a)
        cin >> i, s += i;
    for (ll& i : a)
        i = s - i;
    sort(a.rbegin(), a.rend());
    while (1) {
        ll c = 0, v = a.back();
        while (a.size() && v == a.back())
            a.pop_back(), c++;
        if (c % x == 0) {
            c /= x;
            for (int i = 0; i < c; i++) {
                a.push_back(v + 1);
            }
        } else {
            v = min(v, s);
            cout << fpow(x, v) << "\n";
            return;
        }
    }
}
int main() {
    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);
#ifndef SINGLE_INPUT
    int t;
    cin >> t;
    while (t--) {
        sol();
    }
#else
    sol();
#endif
    return 0;
}