公约数

---

Time Limits: 1000 ms

Memory Limits: 262144 KB

Detailed Limits

---

Description

给定一个正整数\(n\)，在\([1,n]\)的范围内，求出有多少个无序数对\((a,b)\)满足\(gcd(a,b) = a\) \(xor\) \(b\)。

Input

输入共一行，一个正整数\(n\)。

Output

输出共一行，一个正整数表示答案。

Sample Input

3

Sample Output

1

Data Constraint

对于\(30\)%的数据满足\(n\leq1000\)

对于\(60\)%的数据满足\(n\leq1\times10^{5}\)

对于\(100\)%的数据满足\(n\leq1\times10^{7}\)

Hint

只有\((2,3)\)满足要求。

分析

我在打表的时候得出一个结论：满足条件的\(gcd(a,b) = a\)^\(b = a-b\) (设\(a\)为较大数)

此时\(a\)、\(b\)都是\(a-b\)也就是\(gcd(a,b)\)的倍数

我们用\(i\)枚举\(a-b\)，用\(j\)枚举\(a\)，此时\(j\)始终为\(i\)的倍数

这时\(a=j\)，\(b=j-i\)

那么\(a\)^\(b = a-b\)就等价于\(j\)^\((j-i) = i\)

枚举即可 复杂度\(O(nlogn)\)

代码

#include
    
     #include
     
      #define rg register#define int long long using namespace std;inline int read(){    rg int f=0,x=0;    rg char ch=getchar();    while(!isdigit(ch)) f|=(ch=='-'),ch=getchar();    while(isdigit(ch))  x=(x<<1)+(x<<3)+(ch^48),ch=getchar();    return f?-x:x;}int n,ans;signed main() {    n=read();    for(rg int i=1;i<=n;++i)//枚举(a-b)         for(rg int j=(i<<1);j<=n;j+=i)//枚举 a            ans+=((j^(j-i))==i);    printf("%lld",ans);    return 0;}