1

QaQAZ · 2023-07-24 17:06:51 · 个人记录

div3分没div2高，该死的OI赛制

题解都是高效的 \Theta(n\times \log n) 外加 10^8 的预处理，但似乎 \Theta(n\times \dfrac{\sqrt{n}}{\ln(n)}) 更快？

假设 l\times g=\prod a_i ，若 \exists a_i,a_j,\gcd(a_i,a_j)\ne g ，又有 g|\gcd(a_i,a_j) ，故 \gcd(a_i,a_j)>g ，而此时 l 已经在 \prod a_i 的基础上除以了一个 \gcd(a_i,a_j) ，不可能等于 \dfrac{\prod a_i}g ，假设在 \exists a_i,a_j,\gcd(a_i,a_j)\ne g 不成立。

当不存在上述情况，即 \forall a_i,a_j,\gcd(a_i,a_j)= g ，易得 l=\dfrac{\prod a_i}{g^{n-1}} ，当且仅当 n=2 时成立，而 n=2 时必然不存在上述情况，故 n=2 时成立。

综上：

3. 都不满足时，为 No 。

如何判断 a 中是否两两互质？

枚举每一个数，将其分解质因数后塞进一个桶，若后面所有数的质因子在桶里都没有出现过，则两两互质，可以枚举 [1,\sqrt{a_i}] 中的所有质数并直接除下去，若有剩余也必为质数，然后把剩余的质数塞进桶里。

质数大小最大 10^8 ，故应用 map 代替桶。

时间复杂度 \Theta(n\times \dfrac{\sqrt n}{\ln(n)}) ，最慢的点不到 200ms 。

code

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
template<typename T>inline T read(){
    T a=0;bool s=0;
    char ch=getchar();
    while(ch>'9' || ch<'0'){
        if(ch=='-')s^=1;
        ch=getchar();
    }
    while(ch>='0' && ch<='9'){
        a=(a<<3)+(a<<1)+(ch^48);
        ch=getchar();
    }
    return s?-a:a;
}
const int mn=5e6+10;
const int mm=5e6;
int t,n,cnt,a[mn],p[mn],v[mn];
map<int,bool> qaq;
inline void init(){
    for(int i=2;i<=mm;i++){
        if(!v[i])p[++cnt]=i,v[i]=i;
        for(int j=1;j<=cnt;j++){
            if(v[i]<p[j] || i*p[j]>mm)break;
            v[i*p[j]]=p[j];
        }
    }
}
int gcd(int a,int b){return b?gcd(b,a%b):a;}
int main(){
    init();
    t=read<int>();
    for(int cas=1;cas<=t;cas++){
        qaq.clear();
        n=read<int>();
        for(int i=1;i<=n;i++)
            a[i]=read<int>();
        if(n==2){
            puts("Yes");
            continue;
        }
        for(int i=1;i<=n;i++){
            int now=a[i];
            for(int j=1;p[j]*p[j]<=now;j++)
                if(!(now%p[j])){
                    if(qaq[p[j]])goto oO_Oo;//goto后只输出No，正常结束只输出Yes
                    else qaq[p[j]]=1;
                    while(!(now%p[j]))
                        now/=p[j];
                }
            if(now>1){
                if(qaq[now])goto oO_Oo;
                else qaq[now]=1;
            }
        }
        puts("Yes");
        continue;
        oO_Oo:;
        puts("No");
    }
    // while(1)getchar();
    return 0;
}