本文共 891 字，大约阅读时间需要 2 分钟。

回忆一下素数筛选法；

用筛素数法的筛选法求出对于每个a[j]的a[i] % a[j] == 0的个数，然后大于a[j]的区间长度减去a[i] % a[j] == 0的个数，这就是每个对于每个a[j]来说a[i] % a[j] != 0的个数，//因为前者大于后者；然后再乘以a[j]的个数，//有重复的元素；相乘就是这个数与其他数取摸不等于0的个数最后累加一下就好了，注意会爆int//组合数加起来int肯定容不下；

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           using namespace std;//筛选法的应用；；； int main(){ int n, i, j, temp; int m[100006],a[100006]; while(~scanf("%d",&n)) { memset(m,0,sizeof(m)); for(i = 1; i <= n;i++){ scanf("%d",&a[i]); m[a[i]]++;//计算个数；就是计算重复数的个数 } sort(a+1,a+n+1);//排序一下； long long l=0; for(i = 1; i <= n;i++) { if(a[i]!=a[i-1]) { temp=0; for(j = a[i]*2; j <= a[n]; j += a[i])//已经保证前者大于后者了 { temp+=m[j]; } l += (n-i+1-temp-m[a[i]])*m[a[i]]; } } printf("%lld\n",l); } return 0;}
          
         
        
       
      
     
    
   

转载地址：https://blog.csdn.net/zw1996/article/details/52189952 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！