题解：P11818 [PA 2019 Final] 一安在？ / Gdzie jest jedynka? 2

_Rabit_ · 2025-02-26 16:24:27 · 题解

这是一个严格小等于 2n 的做法

一个非常显然的结论。

若 \gcd(a,b) = \gcd(a,c) 则， \gcd(b,c) \ge \gcd(a,b) 。

证明：因为 \gcd(a,b) \mid b,\gcd(a,c) \mid c，所以 \gcd(a,b) 显然是 \gcd(b,c) 的一个因子。

我们又发现，0 和其他数的 \gcd 就是他的 \gcd 最大值，于是不难注意到如果构造一种方法能找到某种意义下的 \gcd 最大值则它必然是某个数和 0 进行的一次 \gcd。

考虑这样一种方法。定义两个指针 l,r 表示当前找到的两个数的下标使得其 \gcd 的值某种意义下最大。接下来枚举一个 i，进行分类讨论。

1. \gcd(a_l,a_i) > \gcd(a_l,a_r)

把 r 赋为 i 。

2. \gcd(a_l,a_i) < \gcd(a_l,a_r)

将 l 赋为 r ，然后将 r 赋为 i。

其实这样并不能求出最大的 \gcd 值，但可以保证 l,r 其中一个是 0。读者自证。最后我们先用 l 求一遍所有数的 gcd，如果出现了两个 1，则用 r 求。

但是我们发现每次情况 3 都会再 ask 一遍 \gcd(a_r,a_i) ，复杂的无法保证。于是我们在求 l,r 时加一点操作：

1. 若 \gcd(a_l,a_i) = 1 则不执行 3 操作。
2. 若出现一对 i,j 被 ask 过，且其 ask 的值 >1 则标记 i,j，使其在最后求 1 的位置时直接跳过。

正确性显然，同时若 \gcd(a_l,a_i) > 1 才有可能会执行 3 操作，多一次 ask，但是 a_i 也会被标记，少一次 ask，所以总次数严格小于等于 2n。

AC code

#include <bits/stdc++.h>
using namespace std;
int ask(int, int);
int solve(int n){
    bool f1 = true,ep = false,en[500010];
    int cnt = 0;//这个是用来验证正确性的
    for(int i = 0;i < n;i++)
        en[i] = true;
    int l = 0,r = 1,vl = ask(l,r);
    cnt++;
    if(vl > 1)en[r] = false,f1 = false;
    for(int i = 2;i < n;i++){
        int vi = ask(l,i);
        cnt++;
        if(vi == 1)continue;
        f1 = false,en[i] = false;
        if(vi == vl)l = r,r = i,vl = ask(l,r),cnt++;
        else if(vi > vl)r = i,vl = vi;
    }
    if(cnt >= 2 * n)exit(0);
    if(f1)return 0;
    int i1 = -1;
    for(int i = 1;i < n;i++){
        if(!en[i])continue;
        if(ep){
            int vi = ask(r,i);
            cnt++;
            if(cnt >= 2 * n)exit(0);
            if(vi == 1)return i;
        }
        else {
            int vi = ask(l,i);
            cnt++;
            if(cnt > 2 * n)exit(0);
            if(vi != 1)continue;
            if(i1 == -1)i1 = i;
            else {
                ep = true;
                int ax = ask(r,i1);
                cnt++;
                if(cnt >= 2 * n)exit(0);
                if(ax == 1)return i1;
                ax = ask(r,i);
                cnt++;
                if(cnt >= 2 * n)exit(0);
                if(ax == 1)return i;
            }
        }
    }
    if(cnt >= 2 * n)exit(0);
    return i1;
}