P2651 添加括号III

分析

传送门

不难发现两个连续分数线就可以将奇数位的数乘在一起数，偶数位的数乘在一起，这是在没有括号的情况下。而有括号的话括号里的计数也从括号前计数，但括号后的计数不计括号里的数

例子：$a_1\ /a_2\ /a_3\ /a_4$

加括号：$a_1/(a_2/a_3)\ /a_4$

变为：$a_1\times a_3\times a_4 \ /a_2$

我们可以发现括号里的计数也从括号前计数也就是说 $a_2$是第二位（偶数位），$a_3$是第三位（奇数位），所以 $a_3$要乘在上面。而括号后的计数不计括号里的数，就是说括号里的东西是第二位，$a_4$是第三位，所以 $a_4$也要乘在上面

发现

当我们的括号如下使用时表达式可以转换成 $\frac{a_1\times a_3\times …\times a_n}{a_2}$

$a_1\ /((((a_2\ /a_3)\ /a_4)\ /a_5)\ /…)\ /a_n$

接着我们发现数据很大，所以不用高精存储不了，但是我们只需要证明结果是整数即可，所以我们可以变读变求最大公约数 $gcd(a_i,a_2)$ 再 $\frac{a_2}{gcd(a_i,a_2)}$，最后如果 $a_2=1$ 那么就说明能约分（即整除）

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
int t,n;
int a_1,a_2,a_x;
int gcd(int a,int b){//不断约分，将分子与分母约分 
  if(a<b)swap(a,b);//方便gcd，大的数除小的数 
  if(!b){
    return a;
  }
  gcd(b,a%b);
}
int main(){
  cin>>t;
  while(t--){
    scanf("%d %d %d",&n,&a_1,&a_2);
    int g_c=gcd(a_1,a_2);
    a_2/=g_c;
    n-=2;//a_1,a_2,单独读处理，后面直接约分就行 
    for(int i=0;i<n;i++){
      scanf("%d",&a_x);
      g_c=gcd(a_x,a_2);
      a_2/=g_c;
    }
    if(a_2==1)cout<<"Yes"<<endl;//可以整除 
    else cout<<"No"<<endl;//不可以 
  }
  return 0;
}