题意: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
     
       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
      
        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