18. （阅读程序）

#include <iostream>

using namespace std;

const int maxn=1010;

void init(int x)
{
    auto lambda_expression=[&](int x,int y)->
    void{
        G[x].emplace_back(y);
    };
    for(int i=1;i<=n;i+=x)
    {
        lambda_expression(i,(i+x-1)%n+1);
    }
}

bool dfs(int u)
{
    if(ins[u]) return 1;
    ins[u]=1;
    bool flag=0;
    for(auto v:G[u])
    {
        if(flag) return 1;
        flag|=dfs(v);
    }
    return flag;
}

int main() 
{ 
    ios::sync_with_stdio(false);
    cin>>n>>m;
    for(int i=1;i<=m;i++)
    {
        int x;
        cin>>x;
        init(x);
    }
    cout<<dfs(1)<<'\n';
}

题目保证输入 1 ≤ n ≤ $10^4$，0 ≤ m ≤ 5 × $10^4$，1 ≤ x_i ≤ n。

（判断题）

本题的时间复杂度为 O(n² ×m )。（ ）

{{ select(1) }}

• 对
• 错

程序空间复杂度为 O(n × $\sum x$)。（ ）

{{ select(2) }}

• 对
• 错

当 n = 1000，m = 2000 的时候，G[1] 的 size 最大为 2000。（ ）

{{ select(3) }}

• 对
• 错

当 n = 1000，m = 2000 的时候，dfs 最大层数为 n + 2。（ ）

{{ select(4) }}

• 对
• 错

（选择题）

程序输入

3 2

1 3

程序输出（ ）

{{ select(5) }}

• 0
• 1
• True
• False

假设 n = 8，输入的 m 个数满足什么性质，才能保证 dfs 函数返回值为 False？（ ）

{{ select(6) }}

• m 个相同的数字
• 一个长度为 m 的排列
• 输入为小于 7 的所有质数（不包括 2）
• 输入为任意两个不互质的数字