专栏文章

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

__Rabit_
P11818题解参与者 3已保存评论 2

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
2 条
当前快照
1 份
快照标识符
@miq4sdfs
此快照首次捕获于
2025/12/03 22:57
3 个月前
此快照最后确认于
2025/12/03 22:57
3 个月前
查看原文

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

一个非常显然的结论。
若 gcd⁡(a,b)=gcd⁡(a,c)\gcd(a,b) = \gcd(a,c) 则，gcd⁡(b,c)≥gcd⁡(a,b) \gcd(b,c) \ge \gcd(a,b) 。
证明：因为 gcd⁡(a,b)∣b,gcd⁡(a,c)∣c\gcd(a,b) \mid b,\gcd(a,c) \mid c，所以 gcd⁡(a,b)\gcd(a,b) 显然是 gcd⁡(b,c)\gcd(b,c) 的一个因子。
我们又发现，00 和其他数的 gcd⁡\gcd 就是他的 gcd⁡\gcd 最大值，于是不难注意到如果构造一种方法能找到某种意义下的 gcd⁡\gcd 最大值则它必然是某个数和 00 进行的一次 gcd⁡\gcd。
考虑这样一种方法。定义两个指针 l,rl,r 表示当前找到的两个数的下标使得其 gcd⁡\gcd 的值某种意义下最大。接下来枚举一个 ii，进行分类讨论。
  1. gcd⁡(al,ai)>gcd⁡(al,ar)\gcd(a_l,a_i) > \gcd(a_l,a_r)
把 rr 赋为 ii 。
  1. gcd⁡(al,ai)<gcd⁡(al,ar)\gcd(a_l,a_i) < \gcd(a_l,a_r)
l,rl,r 保持不变，继续枚举。
  1. gcd⁡(al,ai)=gcd⁡(al,ar)\gcd(a_l,a_i) = \gcd(a_l,a_r)
将 ll 赋为 rr ，然后将 rr 赋为 ii。
其实这样并不能求出最大的 gcd⁡\gcd 值，但可以保证 l,rl,r 其中一个是 00。读者自证。最后我们先用 ll 求一遍所有数的 gcdgcd，如果出现了两个 11，则用 rr 求。
但是我们发现每次情况 33 都会再 askask 一遍 gcd⁡(ar,ai)\gcd(a_r,a_i) ，复杂的无法保证。于是我们在求 l,rl,r 时加一点操作：
  1. 若 gcd⁡(al,ai)=1\gcd(a_l,a_i) = 1 则不执行 33 操作。
  2. 若出现一对 i,ji,j 被 askask 过，且其 askask 的值 >1>1 则标记 i,ji,j，使其在最后求 11 的位置时直接跳过。
正确性显然，同时若 gcd⁡(al,ai)>1\gcd(a_l,a_i) > 1 才有可能会执行 33 操作，多一次 askask，但是 aia_i 也会被标记，少一次 askask，所以总次数严格小于等于 2n2n。

AC code

CPP
#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;
}

评论

共 2 条评论，欢迎与作者交流。

正在加载评论...