「Codeforces 1110C」Meaningless Operations

发表于 | | 阅读次数:
字数统计: 20 字

Description

题目链接：Codeforces 1110C

定义函数 $f(a)$ 的值为：

给出 $q$ 个询问，每个询问为一个整数 $a_i$。你需要对于每个询问，求出 $f(a_i)$ 的值。

数据范围：$1\le q\le 10^3$，$2\le a_i\le 2^{25}-1$

Solution

首先我们可以找到 $f(a)$ 的上界：找到满足 $2^x-1\ge a$ 的最小的 $x$，那么上界就是 $2^x-1$。我们考虑能够构造出这个上界。

我们发现，$\gcd(0,x)=x$，我们用 $\text{bit}_{a,i}$ 表示 $a$ 的第 $i$ 位。构造方式如下：

  • 当 $\text{bit}_{a,i}=0$ 时，$\text{bit}_{b,i}=1$。
  • 当 $\text{bit}_{a,i}=1$ 时，$\text{bit}_{b,i}=0$。

通过如上方式，我们可以使得 $a\oplus b=2^x-1$，使得 $a\ \&\ b=0$，这样一来我们就构造出了上界。

但是考虑特殊情况：当 $a=2^x-1$ 时，这样构造得到的 $b=0$，不满足条件。那么我们考虑异或和与的本质，发现当 $a$ 的所有二进制位都是 $1$ 时，$a\oplus b$ 相当于在 $a$ 中消去 $b$ 的二进制位为 $1$ 的位，$a\ \&\ b$ 相当于在 $a$ 中保留 $b$ 的二进制位为 $1$ 的位。那么我们有：

经过分析，我们可以得到：当 $b$ 为 $a$ 的最大因子的时候，$\gcd(a,b)$ 的值最大（可以直接暴力预处理出所有 $a=2^x-1$ 的函数值）。

当然这题的最好做法当然是打表啦！

时间复杂度：$O(q\log a_i)$（预处理）或 $O(q\sqrt{a_i})$（枚举因子）

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
 
#include <cstdio>

void solve(int x) {
    if(x==3) puts("1");
    if(x==7) puts("1");
    if(x==15) puts("5");
    if(x==31) puts("1");
    if(x==63) puts("21");
    if(x==127) puts("1");
    if(x==255) puts("85");
    if(x==511) puts("73");
    if(x==1023) puts("341");
    if(x==2047) puts("89");
    if(x==4095) puts("1365");
    if(x==8191) puts("1");
    if(x==16383) puts("5461");
    if(x==32767) puts("4681");
    if(x==65535) puts("21845");
    if(x==131071) puts("1");
    if(x==262143) puts("87381");
    if(x==524287) puts("1");
    if(x==1048575) puts("349525");
    if(x==2097151) puts("299593");
    if(x==4194303) puts("1398101");
    if(x==8388607) puts("178481");
    if(x==16777215) puts("5592405");
    if(x==33554431) puts("1082401");
}
int main() {
    int n;
    for(scanf("%d",&n);n--;) {
        int x;
        scanf("%d",&x);
        int cnt=0,tp=0;
        for(int i=0;i<=24;++i) {
            if(x&(1<<i)) tp=i,++cnt;
        }
        if(cnt==tp+1) solve(x);
        else printf("%d\n",(1<<(tp+1))-1);
    }
    return 0;
}
0%