P5949 [BalticOI 2000]Division expression 题解

第一篇可提交的题解，望通过。

下面切入正题。

通过找规律和观察我们发现，要想得到整数，我们应该要选择输入的第二个数，也就是第一个分数的分母作为整体的分母。

那么怎么判断是否可行呢？我们就需要用到约分，即把两个数同时除以它们的最大公约数。

除完之后，如果最终的结果不是一，除不干净，那么就说明它不是整数。

有了思路我们就可以做了。

//~柠月~
#include<bits/stdc++.h>
using namespace std;
int d,n,a[10001],q;//q是第二个数
int gcd(int a,int b)//约分
{
    if(b==0)return a;
    return gcd(b,a%b);
}
int main()
{
    cin>>d;
    for(int i=1;i<=d;i++)
    {
        memset(a,0,sizeof(a));//把a数组初始化
        cin>>n;
        for(int i=1;i<=n;i++)
        {
            cin>>a[i];
        }
        q=a[2];
        for(int i=1;i<=n;i++)
        {
            if(i!=2)q/=gcd(q,a[i]);
        }
        if(q==1)cout<<"YES"<<endl;
        else cout<<"NO"<<endl;
    }
    return 0;
}

不要直接抄代码哦，至少先看看分析吧。