D - Association of Computer Maintenance
题意
给定至多350个小于100的质数，对于所有质数之积k将它分解为两个数a和b使得a*b=k。
输出最小的a+b，并对1e9+7取模
分析
首先考虑想如果想让a+b最小，即让abs(a-b)最小。
随后根据限制条件k的因子数不超过1e10，容易想到将k拆分成k1和k2，此时对于k1和k2的因子数都不超过1e5。
考虑将k1的所有因子存下，最后再枚举k2的所有因子去匹配最接近的k1因子，记录下最小值即可。时间复杂度O(1e5log(1e5))。这边注意维护因子时由于高精度过慢，考虑转换成对数比较大小。
代码实现
c
include <bits/stdc++.h>
int main() {
std::cin.tie(nullptr)->sync_with_stdio(false);
#define int long long
constexpr int P = 1e9 + 7;
std::string str;
std::cin >> str;
std::vector
for (int i = 0; i < (int)str.size(); i += 2) {
pri.emplace_back((str[i] - '0') * 10 + (str[i + 1] - '0'));
}
std::sort(pri.begin(), pri.end());
std::vector<std::pair<int, int>> fac;
for (int i = 0; i < (int)pri.size(); ++i) {
int j = i + 1;
while (j < (int)pri.size() && pri[i] == pri[j]) j += 1;
fac.emplace_back(pri[i], j - i);
i = j - 1;
}
int pos = (int)fac.size() - 1;
for (int i = 0, j = 1; i < (int)fac.size(); ++i) {
if (j * (fac[i].second + 1) > 4e5) {
pos = i - 1;
break;
} else {
j *= fac[i].second + 1;
}
}
auto power = [&](int a, int b) {
int c = 1;
for (; b; b >>= 1, a = a * a % P)
if (b & 1) c = c * a % P;
return c;
};
std::vector<std::pair<int, int>> s;
std::vector<std::pair<double, int>> prod;
int idx = 0;
auto dfs = [&](auto &&self, int u, double diff, int s1, int s2) ->void {
if (u == pos + 1) {
prod.emplace_back(diff, idx++);
s.emplace_back(s1, s2);
return ;
}
auto [p, cnt] = fac[u];
for (int i = 0; i <= cnt; ++i) {
self(self, u + 1, diff + log(p) * (i + i - cnt), s1 * power(p, i) % P, s2 * power(p, cnt - i) % P);
}
};
dfs(dfs, 0, 0, 1, 1);
std::sort(prod.begin(), prod.end());
int ans = 0;
double max = 1e100;
auto find = [&](auto &&self, int u, double diff, int s1, int s2) ->void {
if (u == (int)fac.size()) {
int p = std::lower_bound(prod.begin(), prod.end(), std::pair<double, int>{-diff, -1}) - prod.begin();
if (p < (int)prod.size()) {
auto [w, id] = prod[p];
if (fabs(diff + w) < max) {
max = fabs(diff + w);
ans = (s1 * s[id].first % P + s2 * s[id].second % P) % P;
}
}
if (p - 1 >= 0) {
auto [w, id] = prod[p - 1];
if (fabs(diff + w) < max) {
max = fabs(diff + w);
ans = (s1 * s[id].first % P + s2 * s[id].second % P) % P;
}
}
return ;
}
auto [p, cnt] = fac[u];
for (int i = 0; i <= cnt; ++i) {
self(self, u + 1, diff + log(p) * (i + i - cnt), s1 * power(p, i) % P, s2 * power(p, cnt - i) % P);
}
};
find(find, pos + 1, 0, 1, 1);
std::cout << ans << '\n';
}