题目意思就是给定N个数字,求一个序列,使得sigma(gcd(i,a[i]))的值最小
首先建立个表
比如说
N
6 8 16
这样一组,就是
1 2 3
6: 1 2 3
8: 1 2 1
16:1 2 1
这样一个表.
然后
建立2到N+1这N个节点,代表第N列,建立N+2到N*2+1这N个节点,代表第N行
从2到N+1的每个节点出发,向N+2到N*2+1的这N个节点引一条单向路径,路径的容量是1,费用
是表中的值(就是第I行和J列代表数字的最大公约数),然后建立一个源点1,从1向 2...N+1引
一条
单向路,容量是1,费用是0.
然后建立一个汇点2*N+2,从N+2..N*2+1向N*2+2引一条单向路,容量是1,费用为0,求一下点1
到点N*2+2求一下最小费用最大流,这样最小费用就是所要求的.但是这个算法不好,实际测试
中,地大现场的数据是花了2.8s左右出了所有结果,比赛中还是可以AC的.但是,这个算法没有
用到二分图的某些非常好的性质,所以说复杂度还是比较高的,不过比较容易想到.
方法2:二分