Gym

题意:1e6的数组(1<a[i]<1e6), mul (l,r) =l × (l+1) ×...× r, fac(l,r) 代表 mul(l,r) 中不同素因子的个数,求sigma(i=1 to n) sigma(j=i to n) fac(i,j)

题解:计数套路题,算贡献,直接算有多少区间包含某一个素数的倍数

记录一下所有2的倍数的位置,3的倍数的位置,

之后算有多少个区间包含2倍数的位置,这个就是2这个素数的倍数的贡献,

然后算有多少个区间包含3这个素数的倍数的位置,这个就是3这个素数的贡献。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define mem(a,i) memset(a,i,sizeof(a))
 4 #define rep(i,a,b) for(int i=a;i<=b;++i)
 5 #define pb push_back
 6 typedef long long ll;
 7 const int maxn=1e6+5;
 8 int a[maxn],n;
 9 bool vis[1005];
10 int prim[1005];
11 vector<int> vec[maxn];
12 int cnt;
13 void init() {
14     mem(vis,0);
15     rep(i,0,maxn-1) vec[i].clear();
16     cnt=0;
17     rep(i,2,1004) {
18         if(!vis[i]) {
19             prim[++cnt]=i;
20             for(int j=i*2;j<1005;j+=i) {
21                 vis[j]=1;
22             }
23         }
24     }
25 }
26 int main() {
27     init();
28     scanf("%d",&n);
29     rep(i,1,n) {
30         scanf("%d",&a[i]);
31         int temp=a[i];
32         rep(j,1,cnt) {
33             if(temp<prim[j]) break;
34             if(temp%prim[j]==0) {
35                 vec[prim[j]].pb(i);
36                 while(temp%prim[j]==0) temp/=prim[j];
37             }
38         }
39         if(temp!=1) vec[temp].pb(i);
40     }
41     ll ans=0;
42     rep(i,2,maxn-1) {
43         ll res=1ll*n*(n+1)/2;
44         int len=vec[i].size();
45         if(len==0) continue;
46         rep(j,0,len-1) {
47             if(j==0) res-=1ll*(vec[i][j]-1)*(vec[i][j])/2;
48             if(j==len-1) res-=1ll*(n-vec[i][j])*(n-vec[i][j]+1)/2;
49             if(j+1<len) res-=1ll*(vec[i][j+1]-vec[i][j])*(vec[i][j+1]-vec[i][j]-1)/2;
50         }
51         ans+=res;
52     }
53     printf("%lld
",ans);
54     return 0;
55 }