输入整数n,有多少对整数(a,b)满足:1<=b<=a<=n,且
例如:
n=7,有4对:
(3,2)
(5,4)
(6,4)
(7,6)
要满足的条件为:
枚举a和c,因为a是c的倍数。复杂度是
然后算出b=aXORc,最后验证是否有
总体复杂度为
通过答案得到c = a-b
证明如下:
- 通过gcd性质:a-b >= c
- 通过XOR性质:a-b <= a xor b
可得到c=a-b
.
若a xor b = c
则a xor c = b