提高B组模拟 C

wjh15101051's space

卧薪尝胆，厚积薄发。

提高B组模拟 C

Date: Wed Aug 15 15:15:40 CST 2018

In Category: NoCategory

Description：

求 $[1,n]$ 中有多少个无序实数对 $(a,b)$ 满足 $gcd(a,b)=a\ xor\ b$ .

$1\le n \le 10^7$

Solution：

有性质 $gcd(a,b)\le a-b \le a\ xor\ b$ 。左边不等号显然对，右边每位 $2$ 进制似乎也是满足条件的。

那么我们可以枚举 $gcd(a,b)=k$ 和 $a$ ，则 $b=a+k$ ，只要判断这样是否满足条件就可以了。

复杂度 $\begin{align}O(\sum_{i=1}^n \frac n i)=O(n\ln n)\end{align}$ 。

Code：


#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cstring>

using namespace std;

int n;

int main()

{

	scanf("%d",&n);

	long long ans = 0;

	for(int i = 1;i * 2 <= n;++i)

	{

		for(int p = 1;(p + 1) * i <= n;++p)

		{

			int a = i * p,b = i * (p + 1);

			if((a ^ b) == i)++ans;

		}

	}

	cout << ans << endl;

	return 0;

}

In tag: 其他-其他

wjh15101051