UVA 12716 GCD XOR 【数论】【素数】【暴力枚举】

题目大意

传送门

输入整数n,有多少对整数(a,b)满足:1<=b<=a<=n,且 gcd(a,b)=aXORb

例如:
n=7,有4对:

(3,2)
(5,4)
(6,4)
(7,6)

思路

要满足的条件为: gcd(a,b)=aXORb

  • gcd(a,b)=c 则,a是c的倍数。
  • c=aXORb b=aXORc

枚举a和c,因为a是c的倍数。复杂度是 O(nlog(n))

然后算出b=aXORc,最后验证是否有 gcd(a,b)=c 复杂度为 O(logn)

总体复杂度为 O(n(logn)2)

通过答案得到c = a-b
证明如下:
- 通过gcd性质:a-b >= c
- 通过XOR性质:a-b <= a xor b

可得到c=a-b.

代码

 
 

Hit

若a xor b = c
则a xor c = b
相关文章
相关标签/搜索