题意
给定\(N\)个正整数\(A_1,A_2,\dots, A_N\)。考虑正整数\(B_1, B_2, \dots, B_N\)满足如下条件:
对于任意\(i, j\),有\(1 \leq i < j \leq N, A_iB_i = A_jB_j\)。
求\(B_1+B_2+\dots + B_N\)的最小值,结果对\(10^9+7\)取模。
题目链接:https://atcoder.jp/contests/abc152/tasks/abc152_e
数据范围
\(1 \leq N \leq 10^4\)
\(1 \leq A_i \leq 10^6\)
思路
根据条件,我们可以发现\(A_1B_1 = A_2B_2 = \cdots = A_NB_N\),因此\(B_i = [A_1, \dots, A_N] / A_i\)。
由于最小公倍数数量级较大,因此不能直接相乘去做。因此对\(A_i\)分解质因数即可。
代码
#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <cmath>
#include <map>
using namespace std;
typedef long long ll;
const int N = 10010, mod = 1e9 + 7;
int n;
ll a[N];
map<ll, ll> mp;
ll qmi(ll a, ll b)
{
ll res = 1;
while(b) {
if(b & 1) res = res * a % mod;
a = a * a % mod;
b >>= 1;
}
return res;
}
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++) scanf("%lld", &a[i]);
if(n == 1) printf("1\n");
else {
for(int i = 1; i <= n; i ++) {
ll t = a[i];
for(int j = 2; j <= t / j; j ++) {
if(t % j == 0) {
ll cnt = 0;
while(t % j == 0) {
t /= j;
cnt ++;
}
if(!mp.count(j)) mp[j] = cnt;
else mp[j] = max(mp[j], cnt);
}
}
if(t) {
if(!mp.count(t)) mp[t] = 1;
else mp[t] = max(mp[t], 1ll);
}
}
ll ans = 1;
for(auto p : mp) {
ans = ans * qmi(p.first, p.second) % mod;
}
ll res = 0;
for(int i = 1; i <= n; i ++) {
res = (res + ans * qmi(a[i], mod - 2) % mod) % mod;
}
printf("%lld\n", res);
}
return 0;
}
标签:dots,因式分解,int,res,ll,leq,Flatten,include
From: https://www.cnblogs.com/miraclepbc/p/16723072.html