HDU 5211 Mutiple 水题

题目链接：

http://acm.hdu.edu.cn/showproblem.php?pid=5211

题解：

1、筛法：

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<vector>
 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<int> mat[maxn];
14 
15 void init(){
16     for(int i=0;i<maxn;i++) mat[i].clear();
17     memset(mmp,-1,sizeof(mmp));
18 }
19 
20 int main(){
21     while(scanf("%d",&n)==1&&n){
22         init();
23         int maxa=-1;
24         for(int i=1;i<=n;i++){
25             scanf("%d",a+i);
26             maxa=max(maxa,a[i]);
27             mmp[a[i]]=i;
28         }
29         int ans=0;
30         for(int i=1;i<=n;i++){
31             int minm=INF;
32             for(int j=2;j*a[i]<=maxa;j++){
33                 if(mmp[j*a[i]]!=-1&&mmp[j*a[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
",ans);
41     }
42     return 0;
43 }

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

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #include<algorithm>
 5 #include<vector>
 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
",ans);
33     }
34     return 0;
35 }