备战焦作日常小练之PrimeGame

Given a suqence of nn integers a_iai.

Let \text{mul}(l, r) = \prod_{i = l}^{r} a_imul(l,r)=∏i=lrai and \text{fac}(l, r)fac(l,r) be the number of distinct prime factors of \text{mul}(l, r)mul(l,r).

Please calculate \sum_{i = 1}^{n}\sum_{j = i}^{n}\text{fac}(i, j)∑i=1n∑j=infac(i,j)

Input

The first line contains one integer nn (1 \le n \le 10^61≤n≤106) \text{—}— the length of the sequence.

The second line contains nn integers a_iai (1 \le i \le n, 1 \le a_i \le 10^61≤i≤n,1≤ai≤106) \text{—}— the sequence.

Output

Print the answer to the equation.

样例输入1复制

1
2
10
99 62 10 47 53 9 83 33 15 24

样例输出1复制

1
248

样例输入2复制

1
2
10
6 7 5 5 4 9 9 1 8 12

样例输出2复制

1
134

题目来源

ACM-ICPC Nanjing Onsite 2018

题意

n个数,求所有[i,j]区间内每个数不重复的素数因素之和。

题解

将每个数分解成不同素数之积。例如例1,99分解成3和11,62分解成2和31,10分解成2和5,47分解成47,53为53,9为3,83为83,33为3和11,15为3和5,24为2和3。

第1个数出现次数为n次,第2个为(n-1) 2次,第3个为(n-3) 3次……则素数因数不重复的前提下和母数出现次数相同。但由于某些区间存在相同素数,所以我们规定假设某一位数的素数因数p所在位置为c,上一个这个素数p位置为b,则这次这个素数p出现次数为(n + 1 - c) * (c - b)。当然所以素数的初始位置为0,没出现一次就将该位置更新。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e6+7;
struct NODE{
int size;
ll prime[20];
}node[maxn];
int n;
int pos[maxn];
bool isPrime[maxn];
void init(){
for(ll i = 2; i < maxn; i++){
if(!isPrime[i]){
node[i].prime[node[i].size++] = i;
for(ll j = i+i; j < maxn; j+=i){
isPrime[j] = true;
node[j].prime[node[j].size++] = i;
}
}
}
}
int main(){
init();
scanf("%d", &n);
ll ans = 0;
for(int i = 1; i <= n; i++){
ll tmp;
scanf("%lld", &tmp);
for(int j = 0; j < node[tmp].size; j++){
ans += (ll)(n + 1 - i)*(i - pos[node[tmp].prime[j]]);
pos[node[tmp].prime[j]] = i;
}
}
printf("%lld\n", ans);
return 0;
}

纸短情长啊文章结束了但我们的故事还在继续
坚持原创技术分享,您的支持将鼓励我继续创作!