CF1603A题解

· · 题解

题目大意

给定一个数组 a，每次操作可以删除一个数，当且仅当 a_i \bmod (i+1)\not=0。删除后后面的数字会向前移动，即下标会改变。

题目分析

首先一个性质是若 1\cdots i-1 都可以删除，那 a_i 可以移到 1\cdots i 的任何位置并尝试删除。证明比较简单，从 1 开始依次往后删就能做到。这个不等于 0 的条件不够精准，那么考虑什么时候这个数删不掉，是 a_i \bmod 2=0，a_i \bmod 3=0，\cdots，a_i \bmod (i+1)=0，等价于 a_i \bmod \operatorname{lcm}(2,3,\cdots,i+1)=0。这样可以每次利用 ab=\gcd(a,b)\operatorname{lcm}(a,b) 计算当前的最小公倍数，时间复杂度 O(nlogn)。

注意一直算的话最小公倍数非常大，i 为二十几的时候已经超过了 10^9，所以需要判断跳出去，这样还会跑的更快。

代码

#include<bits/stdc++.h>
#define YPC rubbish 
#define R register
#define I inline
#define ll long long
#define ull unsigned long long
#define LL __int128
#define db double
using namespace std;
#define pb push_back
#define pii pair<int,int>
#define pli pair<ll,int>
#define pll pair<ll,ll>
#define mp(x,y) make_pair(x,y)
#define piii pair<pair<int,int>,int>
#define mp3(x,y,z) make_pair(make_pair(x,y),z)
#define fi first
#define se second
#define putint(x) printf("%d\n",x)
#define putll(x) printf("%lld\n",x)
#define putull(x) printf("%llu\n",x)
#define lowbit(x) ((x)&(-(x)))
#define chkmin(x,y) (x=min(x,y))
#define chkmax(x,y) (x=max(x,y))
#define inv(x) ksm(x,mod-2)
#define inf (1e9)
#define INF (1e18)
#define eps (1e-8)
#define For(i,x,y) for(R int i=x;i<=y;++i)
#define For2(i,x,y,k) for(R int i=x;i<=y;i+=k)
#define Rof(i,x,y) for(R int i=x;i>=y;--i)
#define Rof2(i,x,y,k) for(R int i=x;i>=y;i-=k)
#define ForG(i,edge,x) for(auto i:edge[x])
I int read()
{
    char ch=getchar();
    int res=0,flag=1;
    while(ch<'0'||ch>'9')
    {
        if(ch=='-')
            flag=-1;
        ch=getchar();
    }
    while(ch>='0'&&ch<='9')
    {
        res=res*10+ch-'0';
        ch=getchar();
    }
    return res*flag;
}
int T,n,a[100001]; 
int main()
{
    T=read();
    while(T--)
    {
        n=read();
        bool res=1;
        ll lcm=1;
        For(i,1,n)
            a[i]=read();
        For(i,1,n)
        {
            if(lcm>inf)
                break;
            lcm=lcm*(i+1)/__gcd(lcm,(ll)(i+1));
            if(a[i]%lcm==0)
            {
                res=0;
                break;
            }
        }
        if(res)
            puts("YES");
        else
            puts("NO");
    }
    return 0;
}