三校連訓異或いは題解

イソOR(xor.cpp/.c)【題名説明】正の整数nを与え,[1,n]の範囲内で,gcd(a,b)=a xor bを満たす無系列数対(a,b)がどれだけあるかを求める.【入力フォーマット】合計1行、正の整数nを入力します.【出力フォーマット】出力は1行で、正の整数が答えを表します.【入出力サンプル】【入力サンプル】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)であり、同時に2つの正の整数のgcdは必ずこの2つの数を超えないので、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 
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];
}