最大公约数即为 Greatest Common Divisor，常缩写为 gcd。
一组整数的公约数，是指同时是这组数中每一个数的约数的数。$\pm 1$ 是任意一组整数的公约数。
一组整数的最大公约数，是指所有公约数里面最大的一个。
那么如何求最大公约数呢？我们先考虑两个数的情况。
如果我们已知两个数
不妨设
我们发现如果
我们通过证明可以得到
设
由右边的式子可知
反过来也需要证明：
设 $d \mid b,\mid (a \bmod b)$，我们还是可以像之前一样得到以下式子 $\frac{a\bmod b}{d}=\frac{a}{d}-\frac{b}{d}k,\frac{a\bmod b}{d}+\frac{b}{d}k=\frac{a}{d}$。
因为左边式子显然为整数，所以
既然两式公约数都是相同的，那么最大公约数也会相同。
所以得到式子
既然得到了
详细代码
// C++ Version
int gcd(int a, int b) {
if (b == 0) return a;
return gcd(b, a % b);
}# Python Version
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)递归至 b == 0（即上一步的 a % b == 0) 的情况再返回值即可。
上述算法被称作欧几里得算法（Euclidean algorithm）。
如果两个数
欧几里得算法的时间效率如何呢？下面我们证明，欧几里得算法的时间复杂度为
当我们求
-
$a < b$ ，这时候$\gcd(a,b)=\gcd(b,a)$ ； -
$a \geq b$ ，这时候$\gcd(a,b)=\gcd(b,a \bmod b)$ ，而对$a$ 取模会让$a$ 至少折半。这意味着这一过程最多发生$O(\log n)$ 次。
第一种情况发生后一定会发生第二种情况，因此第一种情况的发生次数一定 不多于 第二种情况的发生次数。
从而我们最多递归
事实上，假如我们试着用欧几里得算法去求 斐波那契数列 相邻两项的最大公约数，会让该算法达到最坏复杂度。
那怎么求多个数的最大公约数呢？显然答案一定是每个数的约数，那么也一定是每相邻两个数的约数。我们采用归纳法，可以证明，每次取出两个数求出答案后再放回去，不会对所需要的答案造成影响。
接下来我们介绍如何求解最小公倍数（Least Common Multiple, LCM）。
一组整数的公倍数，是指同时是这组数中每一个数的倍数的数。0 是任意一组整数的公倍数。
一组整数的最小公倍数，是指所有正的公倍数里面，最小的一个数。
设
我们发现，对于
最小公倍数等于
由于
所以得到结论是
要求两个数的最小公倍数，先求出最大公约数即可。
可以发现，当我们求出两个数的
扩展欧几里得算法（Extended Euclidean algorithm, EXGCD），常用于求
设
由欧几里得定理可知：$\gcd(a,b)=\gcd(b,a\bmod b)$
所以
又因为
所以
因为
将 0 递归 x=1,y=0 回去求解。
详细代码
// C++ Version
int Exgcd(int a, int b, int &x, int &y) {
if (!b) {
x = 1;
y = 0;
return a;
}
int d = Exgcd(b, a % b, x, y);
int t = x;
x = y;
y = t - (a / b) * y;
return d;
}# Python Version
def Exgcd(a, b):
if b == 0:
return a, 1, 0
d, x, y = Exgcd(b, a % b)
return d, y, x - (a // b) * y函数返回的值为
因为迭代的方法避免了递归，所以代码运行速度将比递归代码快一点。
int gcd(int a, int b, int& x, int& y) {
x = 1, y = 0;
int x1 = 0, y1 = 1, a1 = a, b1 = b;
while (b1) {
int q = a1 / b1;
tie(x, x1) = make_tuple(x1, x - q * x1);
tie(y, y1) = make_tuple(y1, y - q * y1);
tie(a1, b1) = make_tuple(b1, a1 - q * b1);
}
return a1;
}如果你仔细观察
最后我们知道
对于正整数
\begin{bmatrix} 0&1\1&-\lfloor a/b\rfloor \end{bmatrix} \begin{bmatrix} a\b \end{bmatrix} $$
其中向下取整符号
易发现欧几里得算法即不停应用该变换，有
\left( \cdots \begin{bmatrix} 0&1\1&-\lfloor a/b\rfloor \end{bmatrix} \begin{bmatrix} 1&0\0&1 \end{bmatrix} \right) \begin{bmatrix} a\b \end{bmatrix} $$
令
\cdots \begin{bmatrix} 0&1\1&-\lfloor a/b\rfloor \end{bmatrix} \begin{bmatrix} 1&0\0&1 \end{bmatrix} $$
那么
\begin{bmatrix} x_1&x_2\x_3&x_4 \end{bmatrix} \begin{bmatrix} a\b \end{bmatrix} $$
满足
int exgcd(int a, int b, int &x, int &y) {
int x1 = 1, x2 = 0, x3 = 0, x4 = 1;
while (b != 0) {
int c = a / b;
std::tie(x1, x2, x3, x4, a, b) =
std::make_tuple(x3, x4, x1 - x3 * c, x2 - x4 * c, b, a - b * c);
}
x = x1, y = x2;
return a;
}这种表述相较于递归更简单。
[!NOTE] AcWing 872. 最大公约数
题意: TODO
[!TIP] 思路
详细代码
#include<bits/stdc++.h>
using namespace std;
int gcd(int a, int b) {
return b ? gcd(b, a % b) : a;
}
int main() {
int n;
cin >> n;
while (n -- ) {
int a, b;
cin >> a >> b;
cout << gcd(a, b) << endl;
}
return 0;
}[!NOTE] AcWing 869. 试除法求约数
题意: TODO
详细代码
#include<bits/stdc++.h>
using namespace std;
vector<int> get_divisor(int x) {
vector<int> res;
for (int i = 1; i <= x / i; ++ i )
if (x % i == 0) {
res.push_back(i);
if (i != x / i) res.push_back(x / i);
}
sort(res.begin(), res.end());
return res;
}
int main() {
int n;
cin >> n;
while (n -- ) {
int x;
cin >> x;
auto res = get_divisor(x);
for (auto x : res) cout << x << ' ';
cout << endl;
}
return 0;
}[!NOTE] LeetCode 650. 只有两个键的键盘
题意: TODO
[!TIP] 思路
详细代码
class Solution {
public:
// 约数做法
// [122...22] [122....22] ... 操作分解
// n = p1 * p2 * ... * pn
// res = p1 + p2 + ... + pn
int minSteps(int n) {
int res = 0;
for (int i = 2; i <= n / i; ++ i )
while (n % i == 0)
res += i, n /= i;
if (n > 1) res += n;
return res;
}
};class Solution {
public:
int minSteps(int n) {
vector<int> f(n + 1, INT_MAX);
f[1] = 0;
for (int i = 2; i <= n; ++ i )
if (n % i == 0)
// 枚举约数
for (int j = 1; j * j <= n; ++ j )
if (i % j == 0) {
f[i] = min(f[i], f[j] + i / j);
f[i] = min(f[i], f[i / j] + j);
}
return f[n];
}
};[!NOTE] LeetCode 1250. 检查「好数组」
题意: TODO
[!TIP] 思路
类似倒水问题
详细代码
class Solution {
public:
bool isGoodArray(vector<int>& nums) {
int n = nums.size();
int res = nums[0];
for (int i = 1; i < n; ++i) res = __gcd(res, nums[i]);
return res == 1;
}
};[!NOTE] LeetCode 1819. 序列中不同最大公约数的数目
题意: TODO
[!TIP] 思路
逆向考虑枚举每一个 GCD 即可
详细代码
ass Solution {
public:
int countDifferentSubsequenceGCDs(vector<int>& nums) {
vector<bool> st(200010);
int mxv = 0;
for (auto v : nums) {
mxv = max(mxv, v);
st[v] = true;
}
int res = 0;
for (int i = 1; i <= mxv; ++ i ) {
int g = -1;
for (int j = i; j <= mxv; j += i)
if (st[j]) {
if (g == -1)
g = j;
else
g = __gcd(j, g); // ATTENTION
}
if (g == i)
res ++ ;
}
return res;
}
};[!NOTE] LeetCode 2001. 可互换矩形的组数
题意: TODO
[!TIP] 思路
double统计即可 对于本题只要保证精度即可边统计边更新记录更稳妥的是使用 gcd
详细代码
class Solution {
public:
using LL = long long;
// wi * hj == wj * hi
long long interchangeableRectangles(vector<vector<int>>& recs) {
unordered_map<double, int> cnt;
LL res = 0;
for (auto rec : recs) {
double w = rec[0], h = rec[1];
res += cnt[w / h];
cnt[w / h] ++ ;
}
return res;
}
};class Solution {
public:
using LL = long long;
LL interchangeableRectangles(vector<vector<int>>& rectangles) {
const int n = rectangles.size();
unordered_map<LL, int> seen;
LL ans = 0;
for (const auto &r : rectangles) {
int w = r[0], h = r[1];
const int g = __gcd(r[0], r[1]);
w /= g; h /= g;
LL hv = (LL)(w) * 100001 + h;
ans += seen[hv];
seen[hv]++;
}
return ans;
}
};[!NOTE] Codeforces Petya and Divisors
题意: TODO
[!TIP] 思路
简单应用 + trick
思维转化并用 last 记录
详细代码
// Problem: B. Petya and Divisors
// Contest: Codeforces - Codeforces Beta Round #85 (Div. 1 Only)
// URL: https://codeforces.com/problemset/problem/111/B
// Memory Limit: 256 MB
// Time Limit: 5000 ms
#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
using PII = pair<int, int>;
const static int N = 1e5 + 10;
int n;
PII a[N];
int last[N];
bool check(int v, int i, int d) {
if (d) {
return last[v] < i - d;
}
return true;
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
memset(last, 0, sizeof last);
cin >> n;
for (int i = 1; i <= n; ++i)
cin >> a[i].x >> a[i].y;
for (int i = 1; i <= n; ++i) {
int t = a[i].x, d = a[i].y, res = 0;
for (int j = 1; j <= t / j; ++j)
if (t % j == 0) {
res += check(j, i, d);
if (t / j != j)
res += check(t / j, i, d);
last[j] = last[t / j] = i;
}
cout << res << endl;
}
return 0;
}[!NOTE] AcWing 1291. 轻拍牛头
题意:
$n$ 个奶牛围成一圈，每个奶牛都绕走一圈，如果该奶牛数值可以被某个奶牛整除则拍这某个奶牛的头求每个奶牛拍其他牛多少次
[!TIP] 思路
反向思路
详细代码
/*
反向：求某个数有多少个数是它的倍数
*/
#include<bits/stdc++.h>
using namespace std;
const int N = 1000010;
int n;
int a[N], cnt[N], s[N];
int main() {
cin >> n;
for (int i = 0; i < n; ++ i ) {
cin >> a[i];
cnt[a[i]] ++ ;
}
for (int i = 1; i < N; ++ i )
for (int j = i; j < N; j += i)
s[j] += cnt[i];
for (int i = 0; i < n; ++ i ) cout << s[a[i]] - 1 << endl;
return 0;
}[!NOTE] AcWing 1294. 樱花
题意:
求有多少正整数数对
$(x,y)$ 满足$\frac{1}{x} + \frac{1}{y} = \frac{1}{n!}$
[!TIP] 思路
原题转化为求
$(n!)^2$ 的约数个数
详细代码
/*
原题转化为求 (n!)^2 的约数个数
*/
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int mod = 1e9 + 7;
const int N = 1000010;
int primes[N], cnt;
bool st[N];
void init(int n) {
for (int i = 2; i <= n; ++ i ) {
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; ++ j ) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
int main() {
int n;
cin >> n;
init(n);
int res = 1;
for (int i = 0; i < cnt; ++ i ) {
int p = primes[i];
int s = 0;
for (int j = n; j; j /= p) s += j / p;
res = (LL)res * (2 * s + 1) % mod;
}
cout << res << endl;
return 0;
}[!NOTE] AcWing 870. 约数个数
题意: TODO
[!TIP] 思路
分解质因子
详细代码
// 求一系列数的乘积的约数个数
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int mod = 1e9 + 7;
int main() {
int n;
cin >> n;
unordered_map<int, int> primes;
while (n -- ) {
int x;
cin >> x;
for (int i = 2; i <= x / i; ++ i )
while (x % i == 0)
x /= i, ++ primes[i];
if (x > 1) ++ primes[x];
}
LL res = 1;
for (auto [v, c] : primes) res = res * (c + 1) % mod;
cout << res << endl;
return 0;
}[!NOTE] AcWing 871. 约数之和
题意: TODO
[!TIP] 思路
$f(n)=(p_1^0+p_1^1+…p_1^a1)(p_2^0+p_2^1+…p_2^a2)…(p_k^0+p_k^1+…p_k^ak)$ 可以乘法逆元加速求积运算
详细代码
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int mod = 1e9 + 7;
int main() {
int n;
cin >> n;
unordered_map<int, int> primes;
while (n -- ) {
int x;
cin >> x;
for (int i = 2; i <= x / i; ++ i )
while (x % i == 0)
x /= i, ++ primes[i];
if (x > 1) ++ primes[x];
}
LL res = 1;
for (auto [v, c] : primes) {
LL t = 1;
// p1^0 + p1^1 + .. + p1^c [共c+1项之和]
while (c -- ) t = (t * v + 1) % mod;
// 累乘积
res = res * t % mod;
}
cout << res << endl;
return 0;
}#include <bits/stdc++.h>
using namespace std;
using LL = long long;
const int MOD = 1e9 + 7;
int n;
int qpow(int a, int b) {
int ret = 1;
while (b) {
if (b & 1)
ret = (LL)ret * a % MOD;
a = (LL)a * a % MOD;
b >>= 1;
}
return ret;
}
int main() {
cin >> n;
unordered_map<int, int> prime;
while (n -- ) {
int x;
cin >> x;
for (int i = 2; i <= x / i; ++ i )
while (x % i == 0) {
x /= i;
prime[i] ++ ;
}
if (x > 1)
prime[x] ++ ;
}
LL res = 1;
for (auto [p, c] : prime) {
// 使用乘法逆元加速计算
// s = a0 * (1 - q^n) / (1 - q)
// n = c + 1;
// 除q-1等于乘q-1的逆元
LL t = (LL)(qpow(p, c + 1) - 1 + MOD) % MOD * qpow(p - 1, MOD - 2) % MOD;
res = res * t % MOD;
}
cout << res << endl;
return 0;
}[!NOTE] AcWing 97. 约数之和
题意: TODO
[!TIP] 思路
约数个数 & 约数之和 公式
本题本身也有公式
详细代码
#include<bits/stdc++.h>
using namespace std;
const int mod = 9901;
int qmi(int a, int k) {
int res = 1;
a %= mod;
while (k) {
if (k & 1) res = res * a % mod;
a = a * a % mod;
k >>= 1;
}
return res;
}
int sum(int p, int k) {
if (k == 1) return 1;
if (k % 2 == 0) return (1 + qmi(p, k / 2)) * sum(p, k / 2) % mod;
return (sum(p, k - 1) + qmi(p, k - 1)) % mod;
}
int main() {
int a, b;
cin >> a >> b;
int res = 1;
// 对a分解质因数
for (int i = 2; i * i <= a; ++ i )
if (a % i == 0) {
int s = 0;
while (a % i == 0) {
a /= i, ++ s;
}
res = res * sum(i, b * s + 1) % mod;
}
if (a > 1) res = res * sum(a, b + 1) % mod;
if (a == 0) res = 0;
cout << res << endl;
return 0;
}[!NOTE] LeetCode 1808. 好因子的最大数目
题意: TODO
[!TIP] 思路
根据题意显然约数个数定理
又因定理累乘显然需要积最大，同减绳子
忘写快速幂 TLE 1
详细代码
class Solution {
public:
// 根据约数个数定理 对 p 分解
// 变为剪绳子的题
using LL = long long;
const LL MOD = 1e9 + 7;
LL quick_pow(LL x, LL k, LL p) {
x %= p;
LL ret = 1;
while (k) {
if (k & 1)
ret = (ret * x) % p;
x = (x * x) % p;
k >>= 1;
}
return ret;
}
int maxNiceDivisors(int p) {
if (p <= 2)
return p;
LL res = 1;
if (p % 3 == 1)
res *= 4, p -= 4;
// 需快速幂
// while (p >= 3)
// res = (res * 3) % MOD, p -= 3;
if (p >= 3) {
LL k = p / 3;
res = (res * quick_pow(3, k, MOD)) % MOD;
p -= k * 3;
}
if (p == 2)
res = (res * 2) % MOD;
return res;
}
};[!NOTE] Luogu 因子和
题意: TODO
[!TIP] 思路
约数和 等比数列求和优化
详细代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
using PII = pair<int, int>;
const int MOD = 9901;
LL a, b;
LL qpow(LL a, LL b) {
// ATTENTION: DO NOT [b %= MOD]
a %= MOD;
LL ret = 1;
while (b) {
if (b & 1)
ret = (ret * a) % MOD;
a = (a * a) % MOD;
b >>= 1;
}
return ret;
}
// 等比数列求和
// sum = (p^n - 1) / (p - 1)
LL smul(LL p, LL s) {
s *= b; // a^b 扩大b倍
s ++ ; // 此时 s = n - 0 + 1
LL t = 0;
if (p % MOD == 1)
t = s % MOD; // 逆元不存在
else
// (p^n-1) * modniv(p-1)
// ATTENTION -1 需要 + MOD 有个case在这里
t = (qpow(p, s) - 1 + MOD) % MOD *
qpow(p - 1, MOD - 2) % MOD;
return t;
}
int main() {
cin >> a >> b;
vector<PII> ve;
for (int i = 2; i <= a / i; ++ i )
if (a % i == 0) {
int t = 0;
while (a % i == 0)
a /= i, t ++ ;
ve.push_back({i, t});
}
if (a > 1)
ve.push_back({a, 1});
LL res = 1;
for (auto [p, s] : ve)
res = res * smul(p, s) % MOD;
cout << res << endl;
return 0;
}[!NOTE] AcWing 877. 扩展欧几里得算法
题意: TODO
[!TIP] 思路
详细代码
/*
ax + by = d
求出一组可行解 x0 y0后 k为任意整数
x = x0 - b / d * k;
y = y0 + a / d * k
*/
#include<bits/stdc++.h>
using namespace std;
int exgcd(int a, int b, int & x, int & y) {
if (!b) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int main() {
int n;
cin >> n;
while (n -- ) {
int a, b;
cin >> a >> b;
int x, y;
exgcd(a, b, x, y);
cout << x << " " << y << endl;
}
return 0;
}[!NOTE] AcWing 878. 线性同余方程
题意: TODO
[!TIP] 思路
拓展欧几里得
详细代码
/*
a * x === b % m
==> ax = my + b
==> ax - my = b
==> ax + my'= b
gcd(a, m) | b 则有解
x = x0 * b / d % m 相当于倍增
*/
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
int exgcd(int a, int b, int & x, int & y) {
if (!b) {
x = 1, y = 0;
return a;
}
int d = exgcd(b, a % b, y, x);
y -= a / b * x;
return d;
}
int main() {
int n;
cin >> n;
while (n -- ) {
int a, b, m;
cin >> a >> b >> m;
int x, y;
int d = exgcd(a, m, x, y);
if (b % d) cout << "impossible" << endl;
else cout << (LL)b / d * x % m << endl;
}
}[!NOTE] LeetCode 780. 到达终点
题意: TODO
[!TIP] 思路
详细代码
class Solution {
public:
bool reachingPoints(int sx, int sy, int tx, int ty) {
while (tx >= sx && ty >= sy) {
if (tx == ty) break;
if (tx > ty) {
if (ty > sy) tx %= ty;
else return (tx - sx) % ty == 0;
} else {
if (tx > sx) ty %= tx;
else return (ty - sy) % tx == 0;
}
}
return sx == tx && sy == ty;
}
};[!NOTE] Luogu [NOIP2000 提高组] 进制转换
题意: TODO
[!TIP] 思路
详细代码
#include <bits/stdc++.h>
using namespace std;
int n, m;
int main() {
cin >> n >> m;
cout << n << "=";
string s;
while (n) {
int mod = n % m;
n /= m;
// ATTENTION
// 出现负数 则从上一位借1
if (mod < 0)
mod -= m, ++n;
if (mod < 10)
s.push_back('0' + mod);
else
s.push_back('A' + (mod - 10));
}
reverse(s.begin(), s.end());
cout << s << "(base" << m << ")" << endl;
return 0;
}[!NOTE] Luogu zzc 种田
题意: TODO
[!TIP] 思路
gcd 的思想
详细代码
#include <bits/stdc++.h>
using namespace std;
using LL = long long;
LL s;
/*
// 1. dfs 直接 MLE
dfs(x, y);
void dfs(LL x, LL y) {
if (x == 0 || y == 0)
return;
if (x < y)
swap(x, y);
// x >= y
s += y * 4;
dfs(y, x - y);
}
*/
/*
// 2. 模拟最后一个点超时
while (x && y) {
if (x < y)
swap(x, y);
s += y * 4;
{
LL nx = y, ny = x - y;
x = nx, y = ny;
}
}
*/
int main() {
LL x, y;
cin >> x >> y;
// 由做法2 考虑优化
// 每次不要只切一个正方形 可以且多个
// 即切 max(x, y) / min(x, y) 个 对应如下情况
// 【长10 宽1】这样的 大幅优化
while (x && y) {
if (x < y)
swap(x, y);
// x >= y
s += y * 4 * (x / y);
x %= y;
}
cout << s << endl;
return 0;
}[!NOTE] LeetCode 1354. 多次求和构造目标数组
题意: TODO
[!TIP] 思路
比赛中好多暴力模拟代码都过了 主要应对两个case
对于 [2] left计算得0 所以最好放在第一行特判
对于 [1,1000000000] 如果当前取出的maxv在处理后还会是maxv 需要考虑：
每次减去的数值都是其他数的值(sum-maxv)=left
因此考虑取余 但要-1因为减后的结果不能是0
【此办法减少循环中操作优先队列的次数】
详细代码
// [2]
// [1,1000000000]
class Solution {
public:
bool isPossible(vector<int>& target) {
if (target.size() == 1) return target[0] == 1;
int n = target.size();
long long sum = 0, maxv, newv, left, y, k;
priority_queue<int> pq;
for (auto v : target) {
sum += v;
pq.push(v);
}
while (!pq.empty() && pq.top() > 1) {
maxv = pq.top();
pq.pop();
// check 新数字
if (2 * maxv - sum < 1) return false;
// 其他数的和为 sum-maxv 新数为 maxv - (sum-maxv) 新sum为 maxv
left = sum - maxv;
/*
if (!pq.empty()) {
y = pq.top();
if (y == 1)
k = (maxv - y + left - 1) / left;
else
k = (maxv - y) / left + 1;
maxv -= k * left;
if (maxv < 1) return false;
sum -= k * left;
}
*/
k = (maxv - 1) / left;
maxv -= k * left;
sum -= k * left;
pq.push(maxv);
}
return true;
}
};[!NOTE] LeetCode 2543. 判断一个点是否可以到达 [TAG]
题意: TODO
[!TIP] 思路
结论：$(1,1)$ 能走到
$(x,y)$ ，当且仅当$x$ 和$y$ 的最大公因数是$2$ 的若干次方。更易理解地：前两种操作不改变横纵坐标的最大公约数，后两种操作可以使得最大公约数乘以
$2$ 。因此我们最终点的横纵坐标的最大公约数是$2$ 的幂次。
详细代码
class Solution {
public:
bool isReachable(int targetX, int targetY) {
while (targetX % 2 == 0)
targetX /= 2;
while (targetY % 2 == 0)
targetY /= 2;
return __gcd(targetX, targetY) == 1;
}
};[!NOTE] LeetCode 2607. 使子数组元素和相等 [TAG]
题意: TODO
[!TIP] 思路
经典结论：对于一个长度为 n 的环，如果环上所有间隔为 k 的元素都要相等，那么环上所有间隔为 gcd(n, k) 的元素都要相等
详细代码
class Solution {
public:
// 经典结论：对于一个长度为 n 的环，如果环上所有间隔为 k 的元素都要相等，那么环上所有间隔为 gcd(n, k) 的元素都要相等
using LL = long long;
LL get(vector<int> & a) {
int n = a.size();
if (n <= 1)
return 0;
sort(a.begin(), a.end());
LL x = a[n / 2], res = 0;
for (auto y : a)
res += abs(y - x);
return res;
}
long long makeSubKSumEqual(vector<int>& arr, int k) {
int n = arr.size();
int d = __gcd(n, k);
// 如果刚好可以划分为整数个周期 则直接算
vector<int> t[d];
for (int i = 0; i < n; ++ i )
t[i % d].push_back(arr[i]);
LL res = 0;
for (int i = 0; i < d; ++ i )
res += get(t[i]);
return res;
}
};[!NOTE] LeetCode 2654. 使数组所有元素变成 1 的最少操作次数 [TAG]
题意: TODO
[!TIP] 思路
理解 gcd 思想
【由于只能操作相邻的数，所以 1 必然是一个连续数组的 GCD】
详细代码
class Solution {
public:
int minOperations(vector<int>& nums) {
int n = nums.size();
// 如果整个数组的 gcd 都不为 1 则永远无法转成全 1
int c = 0;
{
int g = 0;
for (int i = 0; i < n; ++ i )
g = __gcd(g, nums[i]), c += nums[i] == 1;
if (g != 1) // => if (g > 1)
return -1;
}
// 如果原数组存在 1
if (c)
return n - c;
// 数组不存在 1 需要构造 1
// 【考虑 gcd 性质，一定是一个连续区间操作之后形成了一个 1】 => 深刻理解 gcd 性质
// 枚举区间
int minx = n;
for (int i = 0; i < n; ++ i ) {
int t = 0, g = 0;
for (int j = i; j < n && g != 1; ++ j )
g = __gcd(g, nums[j]), t ++ ;
if (g == 1) {
// 执行 t-1 次来构造出一个 1
minx = min(minx, t - 1);
}
}
return minx + n - 1;
}
};[!NOTE] AcWing 200. Hankson的趣味题 [TAG]
题意:
$x$ 和$a0$ 的最大公约数是$a1$
$x$ 和$b0$ 的最大公约数是$b1$ 求
$x$
[!TIP] 思路
枚举d的约数 优化一下 除其所有的质数
2e9 情况下约数只有 1600 个
质数最多只有 50000 个
详细代码
#include<bits/stdc++.h>
using namespace std;
using LL = long long;
const int N =50010;
int primes[N], cnt;
bool st[N];
struct Factor{
int p, s;
}factor[10];
int fcnt;
int dividor[1601], dcnt;
void init(int n) {
for (int i = 2; i <+ n; ++ i ) {
if (!st[i]) primes[cnt ++ ] = i;
for (int j = 0; primes[j] <= n / i; ++ j ) {
st[primes[j] * i] = true;
if (i % primes[j] == 0) break;
}
}
}
void dfs(int u, int p) {
if (u == fcnt) {
dividor[dcnt ++ ] = p;
return;
}
for (int i = 0; i <= factor[u].s; ++ i ) {
dfs(u + 1, p);
p *= factor[u].p;
}
}
int main() {
init(N - 1);
int n;
cin >> n;
while (n -- ) {
int a, b, c, d;
cin >> a >> b >> c >> d;
fcnt = 0;
int t = d;
// 分解质因数
// 复杂度 50000
for (int i = 0; primes[i] <= t / primes[i]; ++ i ) {
int p = primes[i];
if (t % p == 0) {
int s = 0;
while (t % p == 0) t /= p, ++ s ;
factor[fcnt ++ ] = {p, s};
}
}
if (t > 1) factor[fcnt ++ ] = {t, 1};
// 复杂度1600
dcnt = 0;
dfs(0, 1);
// dcnt爆搜得到的所有约数
// 复杂度1600
int res = 0;
for (int i = 0; i < dcnt; ++ i ) {
int x = dividor[i];
if (__gcd(a, x) == b && (LL)c * x / __gcd(c, x) == d) ++ res ;
}
cout << res << endl;
}
return 0;
}