题解：(参考：https://blog.csdn.net/m0_37624640/article/details/83276324)
做法： 计算出来每个数的质因子在各个区间的贡献。 以第二组样例为例：
第一个元素的素因子2： 它能贡献的区间有[1,1]，[1,2]，……，[1,10] 10个区间 第一个元素的素因子3： 它能贡献的区间有[1,1]，[1,2]，……，[1,10] 10个区间 当前sum = 10+10 第二个元素的素因子7： 它能贡献的区间有[1,2]，[1,3]，……，[1,10] 9个区间 它能贡献的区间有[2,2]，[2,3]，……，[2,10] 9个区间 当前sum = 10+10 +9*2 同理第三个元素的素因子5算好后 sum = 10+10+9*2+8*3 当考虑第四元素的素因子5时，发现i = 3时的素因子5 在区间: [1,3]，[1,4]，……，[1,10] [2,3]，[2,4]，……，[2,10] [3,3]，[3,4]，……，[3,10] 这3*8个区间中已经贡献过，所以我们从当前i = 4位置向后考虑 这个位置的素因子5对区间的贡献为 7 sum = 10+10+9*2+8*3+7
最终到n = 10，sum = 10+10+9*2+8*3+7+6*4+5*5+4+0+2*4+1+3=134
#include<set> #include<map> #include<list> #include<queue> #include<stack> #include<math.h> #include<vector> #include<bitset> #include<stdio.h> #include<stdlib.h> #include<string.h> #include<iostream> #include<algorithm> #define eps (1e-8) #define MAX 0x3f3f3f3f #define u_max 1844674407370955161 #define l_max 9223372036854775807 #define i_max 2147483647 #define re register #define nth(k,n) nth_element(a,a+k,a+n); // 将 第K大的放在k位 #define ko() for(int i=2;i<=n;i++) s=(s+k)%i // 约瑟夫 #define ok() v.erase(unique(v.begin(),v.end()),v.end()) // 排序,离散化 using namespace std; inline int read(){ char c = getchar(); int x = 0, f = 1; while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();} while(c >= '0' & c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } typedef long long ll; const double pi = atan(1.)*4.; const int M=1e3+5; const int N=1e6+5; vector<int>vect[N]; void fun(int n,int pos){ if(n==1) return ; if(n==2){ vect[2].push_back(pos); return ; } if(n==3){ vect[3].push_back(pos); return ; } for(int i=2;i*i<=n;i++){ if(n%i==0){ vect[i].push_back(pos); while(n%i==0) n/=i; } } if(n!=1) vect[n].push_back(pos); return ; } int a[N]; int n; ll gun(int d,int pos){ if(vect[d].size()){ int cut=vect[d].back(); cut++; return (ll)(n-pos+1)*(pos-cut+1); } else return (ll)(n-pos+1)*pos; } int main(){ scanf("%d",&n); ll sum=0; for(int i=1;i<=n;i++){ scanf("%d",&a[i]); } ll ans=0; for(int i=1;i<=n;i++){ int d=a[i]; if(d==2||d==3) ans+=gun(d,i); else{ for(int j=2;j*j<=d;j++){ if(d%j==0){ ans+=gun(j,i); while(d%j==0) d/=j; } } if(d!=1) ans+=gun(d,i); } fun(a[i],i); } printf("%lld\n",ans); return 0; }
