GCD

int gcd(int a, int b)
{
	return b ? gcd(b, a % b) : a;
}

典型题目与分析

1. 基础 GCD 题目

   • 题目描述：给定两个整数 a 和 b，求它们的最大公约数。
   • 考查点：直接使用欧几里得算法。
   • 分析：这是最简单的数论题，考查递归或迭代实现欧几里得算法，时间复杂度 $O(\log \min (a,b))$。

2. GCD 与 LCM 的关系

   • 题目描述：给定两个数，要求同时输出它们的最大公约数和最小公倍数。
   • 考查点：利用公式 $\text{lcm}(a,b)=\frac{a\times b}{\gcd (a,b)}$；同时检验对大数运算和溢出问题的处理。
   • 分析：先求 gcd，再计算 lcm。注意要用长整型防止乘法溢出。

3. 数组全局 GCD

   • 题目描述：给定一个数组，求数组中所有元素的 gcd。
   • 考查点：迭代计算多个数的 gcd。
   • 分析：从数组左边第一个元素开始，依次计算 $\text{gcd}(res,a[i])$，时间复杂度 $O(n\log M)$（M 为元素上界）。

4. 区间 GCD 查询

   • 题目描述：给定一个数组和多个区间查询，每个查询询问区间内所有数的 gcd。
   • 考查点：数据结构与数论结合，如用线段树或稀疏表实现区间 gcd 查询。
   • 分析：预处理时间 $O(n\log n)$，每个查询$O(\log n)$（或 O(1) 的稀疏表版本），适合在线查询问题。

5. GCD 累加问题（GCD Sum）

   • 题目描述：求数组中所有满足 $i<j$ 的数对$(a_i,a_j)$ 的 $gcd$ 之和。
   • 考查点：数论求和技巧和分解思路，有时需要反过来统计每个数作为 $gcd$ 的贡献。
   • 分析：直接枚举会超时，通常需要利用筛法或反向思考“对每个可能的公因子统计贡献”，考查对数论性质的深入理解。

void solve()
{
	int n;
	cin >> n;
	// 统计每个因子的频率
	map<int, int> mp;
	vector<int> v(n);
	for (int i = 0; i < n; i++) 
	{
		cin >> v[i];
		mp[v[i]]++;	
	}
 
	// 对每个d 查看数组中有多少个数字 使得d是其因数
	map<int, int> d;
	for (int i = 1; i <= ranges::max(v); i++)
	{
		for (int j = i; j <= ranges::max(v); j += i)
		{
			d[i] += mp[j];
		}
	}
	int ans = 0;
	// 从大到小计算答案 用容斥原理扣除更大因子的贡献
	map<int, int> f;
	for (int i = ranges::max(v); i >= 1; i--)
	{
		auto pr = d[i] * (d[i] - 1) / 2;
		for (int k = 2; k * i <= ranges::max(v); k++)
		{
			pr -= f[k * i];
		}
		ans += i * pr;
		f[i] = pr;
	}
	cout << ans;
}