首页 > 代码库 > 【BZOJ]】1385 [Baltic2000]Division expression

【BZOJ]】1385 [Baltic2000]Division expression

【算法】欧几里德算法

【题解】紫书原题

技术分享
#include<cstdio>
#include<algorithm>
using namespace std;
const int maxn=10010;
int T,t,n,a[maxn];
int gcd(int a,int b)
{return b==0?a:gcd(b,a%b);}
int main()
{
    scanf("%d",&T);
    for(int i=1;i<=T;i++)
     {
         scanf("%d%d%d",&n,&a[1],&t);
         for(int i=2;i<n;i++)scanf("%d",&a[i]);
         for(int i=1;i<n;i++)
          {
              t/=gcd(a[i],t);
              if(t==1)break;
          }
         if(t==1)printf("YES\n");else printf("NO\n");
     }
    return 0;
}
View Code

 

【BZOJ]】1385 [Baltic2000]Division expression