辗转相除法简介
我认为这张动图更容易让人理解一点（来自维基百科辗转相除法）
算法的演示动画。最初的绿色矩形的长和宽分别是a=1071，b=462，从中不断铺上462×462的正方形直到剩下部分面积是462 (b) ×147 (a%b) ；然后再铺上147×147的正方形直至剩下21×147的面积；最后，铺上21×21的正方形时，绿色部分就没有了。即21是1071和462的最大公约数。
思路讲解
主要思路和官方题解一致
A[1] 是所有满足 idx%1==0 的 A[idx] 中最大的；（同时保证字典序以及
ai !=gcd(ai，aj) 因为ai是最大的嘛，你aj都没ai大，最大公因数怎么可能等于ai那）
A[2] 是所有满足 idx%2==0 的 A[idx] 中最大的；
同理，剩下可推。
然后上面我们相当于证明了 j % i == 0的情况（此时最大公倍数为 i ），接下来我们看看j % i ≠ 0 的情况
长话短说，就是我们可以把 j % i ≠ 0 的问题转化为 i % g == 0 的问题，然后又回归到原来这个问题上了
基本就是官方题解思路
其实这个有点像埃氏筛(sieve-like)，所以最后的时间复杂度也和他很像。
筛法的核心代码长这样
1
2
3
4
5
6
7
8
9
10
| for(int i=1;i<=n;++i){
if(idx[i]>m){
cout<<-1<<endl;
break;
}
A[i]=S[idx[i]];
for(int j=2*i;j<=n;j+=i){
idx[j]=max(idx[j],idx[i]+1);
}
}
|
AC代码
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
| #include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll T;
int main() {
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
#ifndef ONLINE_JUDGE
freopen("in.txt","r",stdin);
#endif
cin>>T;
while(T--) {
ll n,m;
cin>>n>>m;
vector<ll> S(m+10);
vector<ll> A(n+10);
bool vis[n+10];
for(int i=1; i<=m; ++i) {
cin>>S[i];
}
sort(&S[1],&S[m+1],greater<ll>());
vector<ll> idx(n+10);
for(int i=1;i<=n;++i){
idx[i]=1;
}
for(int i=1;i<=n;++i){
if(idx[i]>m){
cout<<-1<<endl;
break;
}
A[i]=S[idx[i]];
for(int j=2*i;j<=n;j+=i){
idx[j]=max(idx[j],idx[i]+1);
}
}
if(A[n]==0)
continue;
for(int i=1;i<=n;++i)
cout<<A[i]<<" ";
cout<<endl;
}
#ifndef ONLINE_JUDGE
fclose(stdin);
#endif
}
|
心路历程（WA，TLE，MLE……）
这个比较好，一次提交过，