ErikTse Runtime

  • 首页 / Home
  • | 算法学习 / Algorithm
    • 所有 / All
    • 简单 / Easy
    • 中等 / Medium
    • 困难 / Hard
  • | 技术分享 / Technology
    • 所有 / All
    • 网络技术 / NetWork
    • 资源共享 / Resource
    • 项目实践 / Event
Keep Going.
温故而知新.
  1. 首页
  2. 算法学习
  3. 中等
  4. 正文

[UVa12716]GCD XOR(数论)

2022年9月29日 138点热度 0人点赞 0条评论

题目链接:GCD XOR - UVA 12716 - Virtual Judge (vjudge.net)

最近在看紫书的时候看到这道题,但是感觉紫书上写的有点云里雾里,对于一些“不难发现”的不等式解释不够详细,这里做一下解释。

题目大意 / Problem

给定一个正整数N,问有多少对正整数(A,B)使得\(gcd(a, b) = a\oplus b\),且有\(1 \le B \le A \le N\)。

分析 / Analyse

设\(c = a \oplus b\),则有\(b = a \oplus c\),同时又有\(c = gcd(a, b)\),则我们可以枚举c和a(\(a = k * c\)),然后算出\(b = a \oplus c\),再判断\(1\le B\le N \quad and \quad c=gcd(a, b)\)。这样时间复杂度是\(O(N(logN)^2)\)。N是3e7,非常恐怖,应该会超时。

所以我们继续优化,首先有\(a - b \le a \oplus b\),这个的证明如下:

a-b<=a^b证明

再证明\(a - b \ge gcd(a, b)\)。

所以有c<=a-b<=c,故c=a-b。

这样只需要枚举c和a = k*c,然后算出b = a - c,再判断b = a ^ c即可。

时间复杂度为\(O(NlogN)\)。

因为有多次询问,用前缀和即可。

代码 / Code

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int maxn = 3e7 + 9;
int kase = 0;
int prefix[maxn];

void getprefix(int N)
{
	for(int c = 1;c <= N; ++ c)
	{
		for(int a = c;a <= N; a += c)
		{
			int b = a - c;
			if(1 <= b && b <= a && (a ^ b) == c)prefix[max(a, b)] ++;
		}
	}
	for(int i = 1;i <= N; ++ i)prefix[i] += prefix[i - 1];
}

void solve()
{
	int N;cin >> N;
	cout << "Case " << ++ kase << ": " << prefix[N] << '\n';
}

signed main()
{
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	getprefix(maxn - 5);
	int _;cin >> _;
	while(_ --)solve();
	
	return 0;
}
本作品采用 知识共享署名-非商业性使用 4.0 国际许可协议 进行许可
标签: C++ Uva 数论 算法竞赛
最后更新:2022年9月29日

Eriktse

19岁,性别未知,ACM-ICPC现役选手,ICPC亚洲区域赛银牌选手,CCPC某省赛铜牌蒟蒻,武汉某院校计算机科学与技术专业本科在读。

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

订阅本站
Loading
文章目录
  • 题目大意 / Problem
  • 分析 / Analyse
  • 代码 / Code

COPYRIGHT © 2022 ErikTse Runtime. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang

赣ICP备2022001555号-1

赣公网安备 36092402000057号