GCD

题目链接 Easy version Hard version 题目解法 参考 DeaphetS 的题解 很有意思的题，感觉 \(F1\) 不到 \(*2900\)，\(F2\) 超过 \(*2900\) F1 简化题目中的操作：把 \(n\) 个数放到 \(n-k\) 组中，求 \(\max(\su ......

原题链接：CF1900D，题意不多赘述。 首先可以将 \(a\) 数组排序，并且枚举中间的那个数 \(a_i\)。那么答案就是 \(\sum_{j=1}^{i-1} \gcd(a_j,a_i)\times (n-i)\)。重点在于求前面的 \(\gcd\)。可以用欧拉反演，但是也可以不用，因为我不会 ......

Link 这是一个需要欧拉反演的题目 首先，可以知道只和数字之间的大小有关，数列的顺序无关，那么就可以首先排一个序方便解决该问题。 根据欧拉函数的性质，知道\(n=\sum_{d|n}\phi{(n)}\) 那么我们每次先确定中间的数\(a_j\)，然后根据公式，得他它得贡献是\(\sum_{i=1 ......

\(N\)为上确界，\(n\)为\(a\)数组元素个数，\(D\)为约数个数。 方法一 \(1.\)求出\(d\)，\(d[i]\)表示\(i\)的所有约数（有序）。 时间复杂度：\(O(NlogN)\) vector<int> d[N + 1]; for (int i = 1; i <= N; i ......

洛谷传送门 CF 传送门 不是很懂官方题解在干嘛。 设 \(g_x\) 为满足 \(x \mid \gcd(a_i, a_j, a_k)\) 且 \(i, j, k\) 两两不同的所有无序三元组的 \(f(a_i, a_j, a_k)\) 之和。则很容易容斥求出 \(h_x\) 为 \(x = \g ......

1900D - Small GCD 给定序列 \(A\)，定义 \(f(a, b, c)\) 为 \(a, b, c\) 中最小的次小的数的 \(\gcd\)，求： \[\sum_{i = 1}^n \sum_{j = i + 1}^n \sum_{k = j + 1}^n f(a_i, a_j, ......

2023.11.28 cf上的1900D 容斥原理 先不考虑重叠的情况，把包含于某内容中的所有对象的数目先计算出来，然后再把计数时重复计算的数目排斥出去，使得计算的结果既无遗漏又无重复，这种计数的方法称为容斥原理。 本题思路 由本题数据不难看出暴力枚举肯定超时。 先对数组排序，再在其中找出gcd值为 ......

题目链接：https://codeforces.com/contest/1900/problem/D 对于已经排序好的数组 \(a\)，我们需要计算： \[\sum_{i=1}^n\sum_{j=i+1}^n gcd(a_i, a_j) * (n - j) \]由于 \(\sum_{d|n} \ph ......

Link CF1900 D Small GCD Question 定义 \(f(x,y,z)=\gcd(a,b)\) ，其中 \(a,b\) 为 \(x,y,z\) 中较小的那两个数 给出数组 \(a\)，求 \[\sum\limits_{i=1}^n \sum\limits_{j=i+1}^n \ ......

D. Small GCD Let $a$, $b$, and $c$ be integers. We define function $f(a, b, c)$ as follows: Order the numbers $a$, $b$, $c$ in such a way that $a \le ......

title: 花式求GCD banner_img: https://cdn.studyinglover.com/pic/2023/08/a5e39db5abf0853e6c456728df8bd971.jpg date: 2023-8-2 18:46:00 tags: - 算法 花式求GCD 今天学 ......

洛谷传送门 AtCoder 传送门 喵喵题。 考虑若所有点权都已确定，如何求 \(1\) 到 \(n\) 所有路径权值和的 \(\gcd\)。 考虑如何 check 一个 \(x\) 是否合法。\(x\) 合法的充要条件是，把不能从 \(1\) 到达的点和不能到达 \(n\) 的点扔掉后，存在一组 ......

Description 给定 \(n\) 个点，\(m\) 条边的有向图，图中的任意一条有向边满足 边起点的编号小于边终点的编号。每个点有点权，但其中有些点的点权未知。 你需要找到一种给未知点权值的方案，使得 所有 \(1\to n\) 的路径点权和的最大公因数最大，或者告知答案可以无限大。输出这个 ......

LInk 首先我们可以注意到,两个数的gcd要不是它们当中较小的那一个要不是它本身。 所以对于一个特定的 \(r\),\(gcd_{i=p}^r,1<=p<=r\)来说，答案不会超过32种。 并且因为gcd的性质，答案一定是成块且递减的。 所以我们可以直接记录下对于每一个\(r\),答案都有哪些，从 ......

引言 gcd 有目前几条性质： \(a \cdot b = lcm(a,b) \cdot gcd(a,b)\) \(gcd(a,b) = gcd(b,a-b)\) \(gcd(a,b) = gcd(b,a+b)\) \(gcd(a,b) = gcd(b,a \% b)\) 性质1 \(a \cdot ......

1 OS_object OS_object由下面宏OS_OBJECT_DEC_BASE扩展而来: // 1. os/object.h OS_OBJECT_DECL_BASE(object, NSObject); // 2. os/object.h #define OS_OBJECT_DECL_BAS ......

1 __OBJC__ __OBJC__宏的定义在 GCD 源码中找不到，它定义在 LLVM 的源码中: // initPreprocessor.cpp static void InitializeStandardPredefinedMacros(const TargetInfo &TI, const ......

(EX)GCD 1、给定两正整数m，n 2、选取其中较小的数，假定为m 3、若n%m非0，即存在余数，将n和m中较大的数n替换为余数，返回步骤2 4、若n%m为0，则最大公约数为m #include <stdio.h> int main() { int data1, data2; int data; ......

答案大于max{ai}可以直接计算 主要考虑小于的情况 直接计算gcd很困难，不妨枚举x|gcd 那么对于ai来说 假设 x(k-1)<ai<=xk,那么 ai就需要xk-ai次操作，那么我们对于一个x，只需枚举k计算区间数的个数即可算出需要的操作数。 复杂度O(nlnn) 这种套路就是取模转化成减 ......

题意：给定 \(n\) 求 \(\displaystyle{\sum_{i=1}^n{\sum_{j=1}^n{\left[(i,j)\in prime\right]}}}\) 其中 \(prime\) 为素数集合。 \(n < 10^7\) 解：原式等于 \[\displaystyle{\sum_ ......

UVA12716 一道挺有意思的位运算的题。 \(\gcd(a,b)\) 与 \(a\oplus b\) 本来是没有什么联系的，也不好直接转化。 那么就需要一个中间数进行转化，一般来说会是一个临界值，否则不好找答案。 先观察 \(\gcd(a,b),a\leqslant b\)，可得 \(\gcd( ......

#include<iostream> #include<cstring> using namespace std; const int Maxn=1e7; int phi[Maxn];//记录数的约数个数(欧拉函数) bool vis[Maxn];//记录数字是否访问 int prime[Maxn] ......

给一个正整数 \(n\) 。找到三个不同的正整数 \(a, b, c\) 满足 \(a + b + c = n\) 并且 \(gcd(a, b) = c\) 。 公式归一化简： \[\begin{cases} a + b + c = n, \\ gcd(a, b) = c \end{cases} \ ......

这其实是一道洛谷模板题，题目是5435 对预处理的讲解可以看看[这个博客](https://www.luogu.com.cn/blog/chtholly-willem/solution-p5435)（代码看自己的，见下） ``` void getprime() { for(int i=0;iv[i] ......

[UOJ 传送门](https://uoj.ac/problem/33 "UOJ 传送门") 设 $f_{u, i}$ 为 $u$ 子树内深度为 $i$ 的点的个数，在 $\operatorname{LCA}$ 处计算答案。但是时间复杂度无法接受。 考虑长剖，计算答案只用枚举到轻链长，先对轻儿子做一 ......

## 题意 有一棵有 $n$ 个节点的树，第 $i$ 个节点有点权 $a_i$。 定义 $g(x,y)$ 为 $x$ 到 $y$ 的树上路径所经过的点的点权 $\gcd$。 对于每一个正整数 $k\in[1,2\times 10^5]$ 求出满足以下条件的 $x,y$ 的对数: + $1\le x\ ......

## 题意 对于一个排列 $p$，定义 $g$ 为 $p$ 的前缀最大公约数序列，即 $g_i = \gcd\limits_{j = 1}^{i} p_j$。定义 $f(p)$ 为 $g$ 的元素种类数。 给定 $n$，求长度为 $n$ 的且使得 $f(p)$ 取最大值的排列个数，对 $10^9 + ......

### 题目大意 初始有一个空的集合，和 $Q$ 个操作。对于每个操作，有两种类型，分别用如下的两种形式表示： `1 u`：加入 $u$ 到集合 `2 x k s`：求一个最大的 $v$，使得: 1. $v+x \leq s$ 2. $k \mid \gcd(v,x)$ 3. $x \oplus v ......

# 思路 首先观察到数据范围很大，所以暴力模拟是不可行的，所以我们思考其他的性质。 显而易见地，$X$ 和 $Y$ 一定都是 $N$ 的倍数，所以最大公因数一定都是 $N$ 的倍数。 那么我们可以先将 $X$ 和 $Y$ 除以一个 $N$，那么剩下的就是 $10 \ldots 010 \ldots ......

### 题意 给定一个序列，需要对其进行区间加和和查询 $\gcd$ 操作。 ### 思路 首先看到了区间加和，自然想到是直接打懒标记，但是呢。。。 $\gcd$ 具有一些特殊性，我们并不能通过向下传递标记的方式维护 $\gcd$ 。 于是想到昨天 Tad 讲树状数组区间修改的差分数组方案。 我们创 ......