传送
#pragma GCC optimize(2) #include<bits/stdc++.h> using namespace std; #define pi acos(-1.0) #define e exp(1.0) typedef long long ll; const ll maxn=1e6+7; ll N,cnt; ll a[maxn]; vector<ll>V[maxn];//记录都有哪些数中有这个因子，并存下来他们的数组下标 set<ll>S; set<ll>::iterator it;//存储出现的素因子 void Han(ll j) { ll n=a[j]; ll i; for(i=2;i*i<=n;i++) { if(n%i==0) { V[i].push_back(j); S.insert(i); while(n%i==0) n/=i; } } if(n!=1) { V[n].push_back(j); S.insert(n); } return ; } int main() { // freopen(".../.txt","w",stdout); ios::sync_with_stdio(false); cin>>N; ll i,j; S.clear(); cnt=0; for(i=1;i<=N;i++) cin>>a[i]; for(i=1;i<=N;i++) Han(i); for(it=S.begin();it!=S.end();it++) { for(j=0;j<V[*it].size()-1;j++)//这个算区间的还是要多想想才能明白的 cnt=cnt+(V[*it][j+1]-V[*it][j])*V[*it][j]; if(V[*it].size()) cnt=cnt+(V[*it].back()*(N+1-V[*it].back())); } cout<<cnt<<endl; return 0; }