2018 ICPC 南京区域赛 J - Prime Game（质因数分解）

传送门

题目大意

给出$n$个数，定义$mul(l,r)={\prod }_{i=l}^r{a}_i$，$fac(l,r)$为$mul(l,r)$内不同的质因子个数，求${\sum }_{i=1}^n{\sum }_{j=i}^{n}fac(i,j)$。

解题思路

对于这样需要操作每个区间的问题，常见的思路是固定左端点或者固定右端点，然后不断移动另一端观察区间需要维护问题的变化有无规律，一般来说常见的是有单调性。但是对于本题来说，这样的思路是行不通的。

那么我们考虑另外的思路，首先不难想到对于一段长度为$n$的序列，其所有的子区间的个数为$\frac{n(n+1)}{2}$。然后需要考虑最重要的一点是，每个质因数对一个区间的贡献要么为$1$要么为$0$，我们首先假设所有的质因数对所有区间都有贡献，显然多加了一部分。就是从前向后考虑每种质因数的相邻位置，二者中间的序列是不含有该质因子的，于是这部分是多算的。那么我们只需要遍历每种质因数然后减去多的贡献。

因为每种数的质因数种类数最多只有个位数个，然后我们枚举出现的所有质因数，计算答案即可。

//
// Created by Happig on 2020/11/7
//
#include <bits/stdc++.h>
#include <unordered_map>
#include <unordered_set>
using namespace std;
#define fi first
#define se second
#define pb push_back
#define ins insert
#define Vector Point
#define ENDL "n"
#define lowbit(x) (x&(-x))
#define mkp(x, y) make_pair(x,y)
#define mem(a, x) memset(a,x,sizeof a);
typedef long long ll;
typedef long double ld;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef pair<double, double> pdd;
const double eps = 1e-8;
const double pi = acos(-1.0);
const int inf = 0x3f3f3f3f;
const double dinf = 1e300;
const ll INF = 1e18;
const int Mod = 1e9 + 7;
const int maxn = 1e6 + 10;
int prime[maxn], minp[maxn], all[maxn];
vector<int> fac[maxn], pos[maxn];
bitset<maxn> vis;
int cnt, tot;
void euler() {
for (int i = 1; i <= maxn; i++) minp[i] = i;
for (int i = 2; i < maxn; i++) {
if (minp[i] == i) {
prime[++cnt] = i;
pos[i].push_back(0);
}
for (int j = 1; j <= cnt && 1LL * i * prime[j] < maxn; j++) {
minp[i * prime[j]] = prime[j];
if (i % prime[j] == 0) break;
}
}
}
void divide(int idx, int n) {
tot = 0;
while (n != 1) {
all[tot++] = minp[n];
n /= minp[n];
}
sort(all, all + tot);
int m = unique(all, all + tot) - all;
for (int i = 0; i < m; i++) {
//fac[idx].push_back(all[i]);
//cout << all[i] << " ";
pos[all[i]].push_back(idx);
vis[all[i]] = 1;
}
}
inline ll cal(ll x) {
return x * (x + 1) / 2;
}
bool ok = 0;
ll solve(int p) {
ll ans = 0;
for (int i = 1, l, r; i < pos[p].size(); i++) {
l = pos[p][i - 1] + 1, r = pos[p][i] - 1;
if (l <= r) ans += cal(r - l + 1);
}
return ans;
}
int main() {
//freopen("in.txt","r",stdin);
//freopen("out.txt","w",stdout);
ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0);
int n;
euler();
vis.reset();
cin >> n;
for (int i = 1, x; i <= n; i++) {
cin >> x;
divide(i, x);
}
int num = vis.count();
ll ans = cal(n) * num;
for (int i = 1; i <= cnt; i++) {
if (vis[prime[i]]) {
pos[prime[i]].push_back(n + 1);
ll res = solve(prime[i]);
ans -= res;
}
}
cout << ans << ENDL;
return 0;
}

最后

以上就是妩媚荷花为你收集整理的2018 ICPC 南京区域赛 J - Prime Game（质因数分解）的全部内容，希望文章能够帮你解决2018 ICPC 南京区域赛 J - Prime Game（质因数分解）所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。