咦……这道题怎么这么眼熟呢？

数论经典题……

然后发现我连gcd都不会写了……

代码：

/**************************************************************
    Problem: 1385
    User: danihao123
    Language: C++
    Result: Accepted
    Time:156 ms
    Memory:884 kb
****************************************************************/
 
#include <cstdio>
#include <cctype>
typedef unsigned long long ull;
const int maxn=10001;
ull gcd(ull a,ull b){
    if(b==0)
        return a;
    else
        return gcd(b,a%b);
}
ull A[maxn];
ull fm;
bool solve(int k){
    ull temp;
    register int i;
    for(i=0;i<=(k-2);i++){
        temp=gcd(A[i],fm);
        if(temp==1)
            continue;
        fm/=temp;
        A[i]/=temp;
    }
    return fm==1;
}
template<typename T>
inline T readint(){
    char c=getchar();
    T ans=0;
    while(!isdigit(c))
        c=getchar();
    while(isdigit(c)){
        ans=ans*10+c-'0';
        c=getchar();
    }
    return ans;
}
int main(){
    register int d,k,i;
    d=readint<int>();
    while(d--){
        k=readint<int>();
        A[0]=readint<ull>();
        if(k==0){
            puts("YES");
            continue;
        }
        fm=readint<ull>();
        for(i=1;i<=(k-2);i++)
            A[i]=readint<ull>();
        if(solve(k))
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}

• 相关文章
• 全局相关文章