2018 沈阳 ICPC

#include <cstdio>
#include <cstring>
#include <algorithm>
#include <set>
using namespace std;

const int maxn = 1e6+5;
int a[maxn];
int pos[maxn];
int pri[maxn];
int cnt;

void getpri(int x){
    cnt=0;
    for(int i=2; i*i<=x; i++){
        if(x%i==0){
            pri[++cnt] = i;
            while(x%i==0){
                x/=i;
            }
        }
    }
    if(x>1) pri[++cnt] = x;
}

int main(){
    int n;
    long long ans=0;
    scanf("%d",&n);
    for(int i=1; i<=n; i++){
        scanf("%d",a+i);
    }
    for(int i=1; i<=n; i++){
        getpri(a[i]);
        for(int j=1; j<=cnt; j++){
            int k=pos[ pri[j] ];
            pos[ pri[j] ] = i;
            ans += (long long)(i-k)*(n-i+1);
        }
    }
    printf("%lld\n", ans);
}