ZOJ 4846 GCD Reduce (数学分析题)

?

题意：

给定一个长度为n的数列每次可以选个二元组（a[i],a[j]）换成他们的最大公约数

然后问能不能再5*n次操作内把他们全部换成1,

?

分析：

因为每次操作都是换成GCD 因此n数的GCD肯定为1,如果不为1的话肯定不能变成1的

然后随便构造一种方法就行了，从1到n搞两遍 一定可以全变成1；

?

代码如下：

?

#include 
  
   
#include 
   
     #include 
    
      using namespace std; const int maxn = 1e5+10; int a[maxn]; int gcd(int a,int b) { if(b) return gcd(b,a%b); return a; } int main() { int cas=1,n; while(~scanf(%d,&n)){ int mmin = 1999999999,num=0; for(int i=0;i
     
      
?