最大公约数

https://en.wikipedia.org/wiki/Euclidean_algorithm
https://en.wikipedia.org/wiki/Binary_GCD_algorithm

最大公约数即为 Greatest Common Divisor，常缩写为 gcd。

欧几里得算法

int gcd(int x, int y)
{
    return y > 0 ? gcd(y, x % y) : x;
}

C++中有内置函数__gcd（曾经这个函数不能求 long long）

C++17开始 gcd 和 lcm 成为了内置函数

最小公倍数

int lcm(int x, int y)
{
    return x / gcd(x, y) * y; // 必须先除再乘
    // 易错点！如果写成 x * y / gcd(x, y);
    // 可能乘法越界，但最终结果不越界
    // 1000000000
    // 2000000000
}

二进制求最大公约数的方法

int gcd(int x, int y)
{
    if (x == 0 || y == 0)
    {
        return x + y;
    }
    if (x % 2 == 0 && y % 2 == 0)
    {
        return 2 * gcd(x / 2, y / 2);
    }
    if (x % 2 == 0)
    {
        return gcd(x / 2, y);
    }
    if (y % 2 == 0)
    {
        return gcd(x, y / 2);
    }
    if (x < y)
    {
        swap(x, y);
    }
    return gcd((x - y) / 2, y); // x 和 y 都是奇数， x 大于等于 y， x-y是偶数，可以直接/2
}

每次递归，x和y中至少一个数字变成了自己的一半一下

互质

最大公约数为 $1$ 称之为互质

扩展欧几里得算法

P2152 [SDOI2009] SuperGCD

https://www.luogu.com.cn/problem/P2152

题目描述

Sheng bill 有着惊人的心算能力，甚至能用大脑计算出两个巨大的数的最大公约数！因此他经常和别人比赛计算最大公约数。有一天Sheng bill很嚣张地找到了你，并要求和你比赛，但是输给 Sheng bill 岂不是很丢脸！所以你决定写一个程序来教训他。

输入格式

共两行，第一行一个整数 $a$，第二行一个整数 $b$。

输出格式

一行，表示 $a$ 和 $b$ 的最大公约数。

样例 #1

样例输入 #1

12
54

样例输出 #1

6

提示

数据规模与约定

• 对于 $20\%$ 的数据，有 $0<a,b\le 10^{18}$。
• 对于 $100\%$ 的数据，有 $0<a,b\le 10^{10000}$。

参考代码

题解

P2660 zzc 种田

https://www.luogu.com.cn/problem/P2660

题目背景

可能以后 zzc就去种田了。

题目描述

田地是一个巨大的矩形，然而zzc 每次只能种一个正方形,而每种一个正方形时zzc所花的体力值是正方形的周长，种过的田不可以再种，zzc很懒还要节约体力去泡妹子，想花最少的体力值去种完这块田地，问最小体力值

输入格式

两个正整数x,y，表示田地的长和宽

输出格式

输出最小体力值

样例 #1

样例输入 #1

1 10

样例输出 #1

40

样例 #2

样例输入 #2

2 2 

样例输出 #2

8

提示

1<=x,y<=10^16

参考代码

#include <bits/stdc++.h>
using namespace std;
long long x, y, z;
int main() {
	cin >> x >> y;
	while (y > 0) {
		z += x / y * y * 4;
		x %= y;
		swap(x, y);
	}
	cout << z << endl;
	return 0;
}

题解

P4057 [Code+#1]晨跑

https://www.luogu.com.cn/problem/P4057

题目描述

“无体育，不清华”、“每天锻炼一小时，健康工作五十年，幸福生活一辈子”

在清华，体育运动绝对是同学们生活中不可或缺的一部分。为了响应学校的号召，模范好学生王队长决定坚持晨跑。不过由于种种原因，每天都早起去跑步不太现实，所以王队长决定每$a$天晨跑一次。换句话说，假如王队长某天早起去跑了步，之后他会休息$a-1$天，然后第$a$天继续去晨跑，并以此类推。

王队长的好朋友小钦和小针深受王队长坚持锻炼的鼓舞，并决定自己也要坚持晨跑。为了适宜自己的情况，小钦决定每$b$天早起跑步一次，而小针决定每$c$天早起跑步一次。

某天早晨，王队长、小钦和小针在早起跑步时相遇了，他们非常激动、相互鼓励，共同完成了一次完美的晨跑。为了表述方便，我们把三位同学相遇的这天记为第$0$天。假设三位同学每次晨跑的时间段和路线都相同，他们想知道，下一次三人在跑步时相遇是第几天。由于三位同学都不会算，所以希望由聪明的你来告诉他们答案。

输入格式

输入共一行，包含三个正整数$a,b,c$，表示王队长每隔$a$天晨跑一次、小钦每隔$b$天晨跑一次且小针每隔$c$天晨跑一次。

输出格式

输出共一行，包含一个正整数$x$，表示三位同学下次将在第$x$天相遇。

样例 #1

样例输入 #1

2 3 5

样例输出 #1

30

样例 #2

样例输入 #2

3 4 6

样例输出 #2

12

样例 #3

样例输入 #3

10 100 1000

样例输出 #3

1000

提示

来自 CodePlus 2017 11 月赛，清华大学计算机科学与技术系学生算法与竞赛协会 荣誉出品。

Credit：idea/何昊天 命题/何昊天 验题/卢政荣

Git Repo：https://git.thusaac.org/publish/CodePlus201711

感谢腾讯公司对此次比赛的支持。

参考代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
ll lcm(ll x, ll y)
{
	return x / __gcd(x, y) * y;
}
int main()
{
	ll a, b, c;
	cin >> a >> b >> c;
	cout << lcm(lcm(a, b), c) << endl;
	return 0;
}

题解

输入3个数字，求LCM

abc253_d FizzBuzz Sum Hard

https://atcoder.jp/contests/abc253/tasks/abc253_d
输入n和a和b
问1到n之间所有既不是a的倍数，也不是b的倍数的数字之和是多少？

参考代码

#include <bits/stdc++.h>
using namespace std;
long long n, a, b, c, z;
long long F(long long n)
{
	return n * (n + 1) / 2;
}
int main()
{
	cin >> n >> a >> b;
	c = a / __gcd(a, b) * b;
	z = F(n) - F(n / a) * a - F(n / b) * b + F(n / c) * c;
	cout << z << endl;
	return 0;
}

题解

输入n和a和b
问1到n之间所有既不是a的倍数，也不是b的倍数的数字之和是多少？

全部数字的和
减去a的倍数的和
减去b的倍数的和
加上既是a的倍数又是b的倍数之和

容斥原理

CF1593D1 All are Same

https://codeforces.com/problemset/problem/1593/D1
https://www.luogu.com.cn/problem/CF1593D1

参考代码

题解

CF1166E The LCMs Must be Large

https://codeforces.com/problemset/problem/1166/E
https://www.luogu.com.cn/problem/CF1166E

参考代码

题解

如果输入的集合中，有一对没有交集，那么就无解

CF1107D Compression

https://codeforces.com/problemset/problem/1107/D
https://www.luogu.com.cn/problem/CF1107D

参考代码

题解