备战焦作日常小练之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复制

样例输入2复制

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

样例输出2复制

题目来源

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，没出现一次就将该位置更新。

#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;
}