[TOYOTA 2023 Spring Final C] Count Dividing XOR 题解

· · 题解

神仙数学题，有数学竞赛那味了。

有一个重要结论：A\oplus B=B-A，这里 \oplus 表示按位异或。证明如下：

\because A\oplus B|A, A\oplus B|B, \therefore A\oplus B|B-A\Rightarrow A\oplus B\le B-A, \because A\oplus B\ge B-A, \therefore A\oplus B=B-A.

所以只用枚举 A\oplus B（即 B-A），然后枚举可能的 A 即可。令 D=R-L，则时间复杂度 O(D\log D)。

放代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
main(){
  ios::sync_with_stdio(false);
  int l,r,c=0; cin>>l>>r;
  for(int i=1;i<=r-l;i++) // 枚举 A^B
    for(int j=(l+i-1)/i*i;i+j<=r;j+=i)
      c+=(j^i+j)==i; // 如果 j 和 i+j 的异或值为 i，那么这个答案就是合法的
  cout<<c<<endl;
  return 0;
}