题目链接：

题解：

1、筛法：

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7  8 const int maxn=10000+10; 9 const int INF=0x3f3f3f3f;10 11 int n;12 int a[maxn],mmp[maxn];13 vector
          
            mat[maxn];14 15 void init(){16 for(int i=0;i
           
            i){34 minm=min(minm,mmp[j*a[i]]);35 } 36 }37 if(minm==INF) minm=0;38 ans+=minm;39 }40 printf("%d\n",ans);41 }42 return 0;43 }
           
          
         
        
       
      
     

2、倒着扫回来，不断刷新约数的值

1 #include
     
       2 #include
      
        3 #include
       
         4 #include
        
          5 #include
         
           6 using namespace std; 7  8 const int maxn=10000+10; 9 const int INF=0x3f3f3f3f;10 11 int n;12 int a[maxn],mmp[maxn];13 14 void init(){15     memset(mmp,0,sizeof(mmp));16 }17 18 int main(){19     while(scanf("%d",&n)==1&&n){20         init();21         for(int i=1;i<=n;i++) scanf("%d",a+i);22         int ans=0;23         for(int i=n;i>=1;i--){24             ans+=mmp[a[i]];25             for(int j=1;j*j<=a[i];j++){26                 if(a[i]%j==0){27                     mmp[j]=i;28                     mmp[a[i]/j]=i;29                 }30             }31         }32         printf("%d\n",ans);33     }34     return 0;35 }