【题解】UVA12716 GCD XOR

wsyhb · 2021-01-10 20:12:24 · 题解

题意简述

（T 组询问）给定正整数 n，问满足下列条件的有序对 (a,b) 的个数：

• 1 \le b \le a \le n
• \gcd(a,b)=a \; xor \; b

数据范围：T \le 10^4，n \le 3 \times 10^7

分析 + 题解

题目给出的条件是 \gcd 和异或值相等，两者似乎没有任何联系，考虑用一个中间变量来进行转换。

由样例解释可知，n=7 时共有这四对：(3,2)，(5,4)，(6,4) 和 (7,6)。我们发现这几对的异或值与它们的差相等，继续枚举 n=10 的其它满足条件的有序对，发现仍满足此条件，即 \gcd(a,b)=a-b=a \; xor \; b。接下来尝试证明此结论。

首先，显然有 a \neq b，则 \gcd(a,b)=\gcd(a-b,b) \le a-b；

其次，显然有 a \; xor \; b \ge a-b，当且仅当 a \; and \; b=b 时取等—— a 为 1 的二进制位只有当 b 这一位也为 1 时才可能变为 0。

综上，有 \gcd(a,b) \le a-b \le a \; xor \; b，则两个等号都必须取到，证毕。

由于 a 和 b 均为 a-b 的倍数，我们可以枚举 k=a-b，并枚举 k 的倍数作为 b，再验证 a \; and \; b=b 是否成立即可。由于有多组询问，我们需要预处理 \max\{n\} 的答案的差分数组，并通过前缀和来求得所有 n 的答案。

代码

#include<bits/stdc++.h>
using namespace std;
int range;//max{n}
const int max_n=3e7+5;
long long ans[max_n];
inline void init()
{
    for(int k=1;k<=range;++k)
        for(int b=k;b+k<=range;b+=k)//按照上述方法枚举 
        {
            int a=b+k;
            if((b&a)==b)//注意运算优先级，要打括号 
                ++ans[a];//此处差分，表示所有 >=a 的 n 的 ans++ 
        }
    for(int i=1;i<=range;++i)
        ans[i]+=ans[i-1];//差分求前缀和 
}
const int max_T=1e4+5;
int n[max_T];
int main()
{
    int T;
    scanf("%d",&T);
    for(int i=1;i<=T;++i)
    {
        scanf("%d",n+i);
        range=max(range,n[i]);
    }
    init();
    for(int i=1;i<=T;++i)
        printf("Case %d: %lld\n",i,ans[n[i]]); 
    return 0;
}