【SWTR-01】Sweet Round 01 T1 Escape

Alex_Wei · 2019-10-02 19:28:42 · 题解

\color{orange}\text{题面}

官方题解

结论水题，部分分留给你们瞎打的（逃

结论：设所有的可行步数为 b_1,b_2, \dots ,b_x

• 如果 gcd(b_1,b_2,\dots,b_x,n)=1，则答案为 n

• 否则不可行，输出 -1

注意到 k\leq n 而不是 k<n

如果 n=k，那么答案肯定是 -1

看看你有没有特判下面这组数据

input
1
1 1
1
output
-1

解析：

设 d=gcd(b_1,b_2,\dots,b_x,n)

• 如果 d>1，易知不可能完成，即只能跳到编号为 d 的倍数的平台

易知 “如果有一个 b_i 与 n 互质，就可以用 n 步跳遍所有平台”

现在需要证明 "如果 d=1，则一定能走遍所有平台，且步数为 n”

（注：以下为这道题目结论的证明，并不是的真正实现方法）

设 d_1=gcd(b_1,n)

如果 d_1=1，则可以完成任务（跳 n 次即可）

否则只能跳到 编号是 d_i 倍数的平台上

接下来是很重要的一点！

• 如果我们能跳到 mod\ d_1=1 的任意一个平台，mod\ d_1=2 的任意一个平台，\dots，mod\ d_1=d_1-1 的任意一个平台，那么我们就能跳到所有平台

因为如果你跳到了任意一个 mod\ d_1=i 的平台上，那么你就能跳到 所有 mod\ d_1=i 的平台上(每次跳 b_1 个)

例如 b_1=3,b_2=4,n=12

跳 4 步 3\ ->0,3,6,9,pos=0\ (0\ mod\ 3=0)

跳 1 步 4\ ->0,3,4,6,9,pos=4\ (4\ mod\ 3=1)

跳 3 步 3\ ->0,1,3,4,6,7,9,10,pos=1

跳 1 步 4\ ->0,1,3,4,5,6,7,9,10,pos=5\ (5\ mod\ 3=2)

跳 3 步 3\ ->0,1,2,3,4,5,6,7,8,9,10,11,pos=2

这样，问题就从原来的

被简化成了 b_2,b_3,\dots,b_x 遍历所有 d_1

又因为 d=1，所以 必定有一次 gcd(b_i,d_{i-1})=1，于是就能完成任务啦 qwq

有了结论，代码可好打了：

/*
DO NOT CHEAT!
author : Alex_Wei 
time : 2019.9.13
language : C++
*/
#include<bits/stdc++.h> 
using namespace std;
/*
快读 
inline void read(int &x)
{
    x=0;char s=getchar();
    while(!isdigit(s))s=getchar();
    while(isdigit(s))x=(x<<1)+(x<<3)+s-'0',s=getchar();
}
*/
int t,a[19260817];
bool pd[19260817];
int gcd(int a,int b){return !b?a:gcd(b,a%b);}
int main()
{
    scanf("%d",&t);
    for(int l=0;l<t;l++){
        int n,k,d;
        scanf("%d%d",&n,&k),d=n;
        for(int i=1;i<=k;i++)
            scanf("%d",&a[i]),pd[a[i]]=1;//标记一下
        if(n==1&&k==1){cout<<"-1\n",pd[1]=0;continue;}//特判 n=k=1 的情况
        for(int i=1;i<=n;i++)
            if(!pd[i])//如果可以走，求 gcd
                d=gcd(d,i);
        if(d>1)cout<<"-1\n";//d>1 
        else cout<<n<<endl;
        for(int i=1;i<=k;i++)
            pd[a[i]]=0;//取消标记，不然 memset （可能会）超时
    }
    return 0;
}