三校连训 异或 题解

异或
（xor.cpp/.c）
【题目描述】
给定一个正整数 n，在 [1,n]的范围内，求出有多少个无序数对(a,b)满足 gcd(a,b)=a xor b。
 
【输入格式】
输入共一行，一个正整数 n。
【输出格式】
输出共一行，一个正整数表示答案。
【输入输出样例】
【输入样例】
3
【输出样例】
1
【样例解释】
只有(2,3)满足要求。
【数据范围】
对于 30%的数据，n≤1000。
对于 60%的数据，n≤10^5。
对于 100%的数据，n≤10^7。

题目大意：给定n，求[1,n]中有多少个gcd(a,b)==a^b;（无序）；

假设a>b,我们知道gcd(a,b)=gcd(a-b,b)，同时两个正整数的gcd一定不会超过这两个数，所以gcd(a,b)≤a-b

设a的第i位为x，b的第i位为y。

当x=1或者x=y=0时，都有x-y=x xor y。

当x=0且y=1时，有x xor y=1，x-y=-1，即x xor y>x-y。

于是，我们得出a xor b≥a-b。

所以gcd(a,b)=a^b=a-b;

设c=a-b，那么有gcd(a,a-c)=c，即我们需要满足a是c的倍数且a≠c

复杂度：在[1,n]内i的倍数有[n/i]个，所以复杂度为：nlogn;

#include <bits/stdc++.h>
using namespace std;
int f[10000001];
int main()
{
    int n;
    cin>>n;
    for(int i=1;i<=5000000;i++){
        for(int j=i*2;j<10000000;j+=i){
            int b=j-i;
            if((j^b)==i) f[j]++;
        }
    }
    for(int i=1;i<=n;i++) f[i]+=f[i-1];
    cout<<f[n];
}