题意

给定 n,求二元组 (a,b) 满足 1\le a\le b\le n\gcd(a,b)=a \operatorname{xor} b 的个数

思路

假设 a\ge b,注意到 a \operatorname{xor} b=ca \operatorname{xor} c=b。而异或运算相当于一个不进位的加减法,故满足 a-b \le a\operatorname{xor}b\le a+b

a>b 时,\gcd(a,b)=m,则 a=k_1 mb=k_2mk_1> k_2,故 a-b=m(k_1-k_2)>m=\gcd(a,b)

综上,a-b\le \gcd(a,b) \le a-b,故 a-b=\gcd(a,b)=a\operatorname{xor} b

由于 m=\gcd(a,b),所以 m\mid a m\mid b。计算时先枚举 m 再枚举 m 的倍数即可。

#include <cstdio>

const int maxn=30000000+5;
long long f[maxn+5];

int main()
{
    int t,n;
    scanf("%d",&t);
    for(int c=1;c<=maxn;++c)
        for(int a=c<<1;a<=maxn;a+=c)
            if((a^(a-c))==c)//即(a^b)==c,b=a-c
                ++f[a];
    for(int i=1;i<=maxn;++i)
        f[i]+=f[i-1];
    for(int kase=1;kase<=t;++kase)
    {
        scanf("%d",&n);
        printf("Case %d: %lld\n",kase,f[n]);
    }
    return 0;
}
最后修改日期:2020年11月29日

作者

留言

撰写回覆或留言

发布留言必须填写的电子邮件地址不会公开。