本文共 2266 字，大约阅读时间需要 7 分钟。
当 i = j i = j i=j 时，条件 gcd ( i , j ) = i x o r j \gcd(i,j)=i\;xor\;j gcd(i,j)=ixorj 不可能成立，钦定 i > j i>j i>j。 分析： ∵ \because ∵ gcd ( i , j ) = gcd ( i − j , j ) , gcd ( i − j , j ) ≤ i − j \gcd(i,j)=\gcd(i-j,j),\;\gcd(i-j,j)\leq i-j gcd(i,j)=gcd(i−j,j),gcd(i−j,j)≤i−j ∴ \therefore ∴ gcd ( i , j ) ≤ i − j \gcd(i,j)\leq i-j gcd(i,j)≤i−j ∵ \because ∵ 异或相当于不退位的减法 ∴ \therefore ∴ i x o r j ≥ i − j i\;xor\;j\geq i-j ixorj≥i−j ∴ \therefore ∴ gcd ( i , j ) ≤ i − j ≤ i x o r j \gcd(i,j) \le i-j \le i \; xor \; j gcd(i,j)≤i−j≤ixorj ∵ \because ∵ gcd ( i , j ) = i x o r j , gcd ( i , j ) ≤ i − j ≤ i x o r j \gcd(i,j)=i\;xor\;j,\;\gcd(i,j) \le i-j \le i \; xor \; j gcd(i,j)=ixorj,gcd(i,j)≤i−j≤ixorj ∴ \therefore ∴ i x o r j = i − j i \; xor \; j =i-j ixorj=i−j ∴ \therefore ∴ 问题变成了 ∑ i = 1 n ∑ j = i n [ i x o r j = = i − j ] \sum_{i=1}^n\sum_{j=i}^n[i\;xor\;j==i-j] ∑i=1n∑j=in[ixorj==i−j] 然而直接暴力枚举 i i i 和 j j j 任会超时。
∵ \because ∵ gcd ( i , j ) = i x o r j , i x o r j = i − j \gcd(i,j) = i\;xor\;j,\;i \; xor \; j =i-j gcd(i,j)=ixorj,ixorj=i−j ∴ \therefore ∴ gcd ( i , j ) = i − j \gcd(i,j) =i-j gcd(i,j)=i−j ∵ \because ∵ gcd ( i , j ) = gcd ( i , i − j ) \gcd(i,j) =\gcd(i,i-j) gcd(i,j)=gcd(i,i−j) ∴ \therefore ∴ gcd ( i , i − j ) = i − j \gcd(i,i-j)=i-j gcd(i,i−j)=i−j ∴ \therefore ∴ i i i 为 i − j i-j i−j 的倍数 ∴ \therefore ∴ 我们只需枚举 j j j，再枚举 j j j 的倍数 i i i，再判断 i x o r j = i − j i \; xor \; j =i-j ixorj=i−j 就行。 然而还是会超时······
于是就需要预处理出 a n s ans ans：
for(int j=1; j<=Max/2; j++) for(int i=j<<1;i<=Max;i+=j) if((i^j)==i-j) ans[i]++;
再求前缀和：
for(int i=2;i<=Max;i++) ans[i]+=ans[i-1];
a n s [ i ] ans[i] ans[i]表示 i i i为 1 1 1~ i i i的答案。
贴上十分简短的代码：
#include#include #define Max 30000001#define Max2 15000000using namespace std;int t,n,ans[Max+5];int main(){ for(int j=1; j<=Max2; j++) for(int i=j<<1;i<=Max;i+=j) if((i^j)==i-j) ans[i]++; for(int i=2;i<=Max;i++) ans[i]+=ans[i-1]; scanf("%d",&t); for(int i=1; i<=t; i++) { scanf("%d",&n); printf("Case %d: %d\n",i,ans[n]); }}
转载地址：http://nhpwb.baihongyu.com/