题目内容
给定一个长度为n的数组{a1,a2,…,an},定义数组的权值为数组所有元素之和。你可以执行任意次以下操作,以使数组权值最小化:
- 选择两个索引 i 和 j ;
- 任意选取两个正整数 x 和 y ,但需满足 gcd(x,y)=gcd(ai,aj);
题解
题面描述
给定一个长度为 n 的数组 {a1,a2,…,an},定义数组的权值为数组所有元素之和。你可以执行任意次以下操作,以使数组权值最小化:
- 选择两个索引 i 和 j;
- 任意选取两个正整数 x 和 y,但需满足gcd(x,y)=gcd(ai,aj);
- 将 ai←x,aj←y。