GCD
CF1575G GCD Festival 题解
## 题意 给定一个长度为 $n$ 的正整数数列 $a$，求 $$\sum\limits_{i = 1}^{n}\sum\limits_{j = 1}^{n} \gcd\left(a_i, a_j\right) \times \gcd\left(i, j\right)$$ （$1 \le n,a_i ......
CF1762D GCD Queries 题解
## 题面 给定一个长度为 $n$ 的排列 $0, 1, \cdots, n - 1$。可以进行最多 $2n$ 次询问，每次询问给出两个下标 $i, j$，交互器会返回 $\gcd(p_i, p_j)$。询问以后，需要输出两个下标 $x, y$，满足 $p_x = 0 \lor p_y = 0$。特 ......
CF803C Maximal GCD 题解
## 题意 构造一个长度为 $k$，和为 $n$ 的严格单调递增序列，并最大化其最大公约数。 （$1 \le n,k \le 10^{10}$） ## 题解 首先可以发现一个事实，这个序列的最大公约数一定为 $n$ 的因子。所以我们可以考虑枚举 $n$ 的所有因子并判断其能否成为整个序列的最大公约数 ......
[ARC126C] Maximize GCD
设 $a_x$ 为数列 $a$ 中的最大值。 一般来说，与其处理 $x | \gcd(A_1,\dots,A_N)$ ，处理 $x = \gcd(A_1,\dots,A_N)$ 更加容易。这是因为后者能够被分解为各个元素：$\forall i,x | A_i$。 因此，我们将解决下面这个问题而不是原 ......
CF1513D GCD and MST 题解
## 题面 对于一个序列，若有 $(i,j)(i typedef long long valueType; typedef std::vector ValueVector; typedef std::pair ValuePair; typedef std::vector PairVector; ty ......
[ARC126C] Maximize GCD 题解
## 题意 给定一个序列 $A$，每次操作可以使 $A_i + 1$（$i \in \left[1, n\right]$，$K$ 次操作的 $i$ 可以不同），最多可以做 $K$ 次。问 $\gcd{A_1, A_2, ..., A_n}$ 的最大值。 ## 题解 首先，如果 $K$ 可以把当前序列 ......
莫比乌斯反演 & gcd 卷积
没有写一些概念（？（（（ 我是梅比乌斯厨=莫比乌斯厨=牲畜（暴论。 ### 前置芝士 #### 积性分解 对于积性函数 $f$，给出 $n=\prod_{i=1}^m p_i^{c_i}$。有 $f(n)=\prod_{i=1}^m f(p_i^{c_i})$。意思是跟 质因子 & 幂次 相关度较高 ......
P2568 GCD
## Question 问题 [P2568 GCD](https://www.luogu.com.cn/problem/P2568) $$ \sum_{p\in prime}\sum_{i=1}^n \sum_{j=1}^n [\gcd(i, j)==p] $$ ## Analysis 分析 1 （ ......
P2257 YY的GCD
[传送门](https://www.luogu.com.cn/problem/P2257) 首先得到一个非常显然的柿子 $$ \sum_{p} \sum_{d} \lfloor\frac{n}{pd}\rfloor \lfloor\frac{m}{pd}\rfloor $$ 我们可以考虑T=pd，然 ......
GCD
> [GCD 洛谷](https://www.luogu.com.cn/problem/P9484) 题目描述 一张图有 $n$ 个节点，编号为 $1,2,3,\dots,n$。其中 $i$ 号节点会向 $j$ 号节点连一条边权为 $|i-j|$ 的无向边，当且仅当 $\gcd(i,j)=i,\op ......
hdu7319 String and GCD
[String and GCD](https://acm.hdu.edu.cn/showproblem.php?pid=7319) 首先我们需要用kmp的fail建树，然后需要利用到欧拉反演。 $$n=\sum_{d|n} \varphi(d)$$ 对于这题来说 $$(i,j)=\sum_{d|(i ......
P8443 gcd.
与你借星火，容我题山河。 ### 一.题目大意 原题要我们求 $\operatorname{gcd}\left(\left\lfloor\frac{l}{x}\right\rfloor,\left\lfloor\frac{l+1}{x}\right\rfloor, \cdots,\left\lflo ......
题解 HDU5726【GCD】/ LGT353762【Soso 的最大公约数】
## Problem 给你一个长为 $N(1\leq N \leq 1\times 10^5)$ 的整数序列：$a_{1},\cdots,a_{n}(0 原题 ```cpp #include #include #include #include #include using namespace st ......
欧几里得算法求解最大公因数（gcd）正确性的证明
# 欧几里得算法求解最大公因数（gcd）正确性的证明 欧几里得算法是求解最大公因数（gcd）的简单且高效的算法。它的求解方法是以下的一个递归式： $$ \gcd(a, b) = \begin{cases} a & b = 0 \\ \gcd(b, a\bmod b) & b \neq 0 \end{ ......
UVA12716 GCD等于XOR GCD XOR
UVA12716 GCD等于XOR GCD XOR 一道数学题。 首先，我们可以知道，a-b>=gcd(a,b)=c; 其次，a-b<=a xor b=c; 综上，可得a-b=c,即a-b=a xor b. 由于范围不大，直接枚举。 第一层枚举c（因为c较少），第二层枚举a，（b=a-c) 再判断c ......
[数论]Divisor and Gcd
## Divisor and Gcd ### 1、算术基本定理：n的质因数分解唯一 一些常见结论： 1.素数无限 2.$\lim_{n\rightarrow+\infty}n\prod\dfrac{n}{\frac{n}{\ln{n}}}$(Π(n)表示 ab|c$ 3.$a|bc,(a,b) = ......
[ABC162E] Sum of gcd of Tuples (Hard)
## 题面翻译 给定$n,k$，求 $$\sum^k_{a_1=1}\sum^k_{a_2=1}\sum^k_{a_3=1}\dots\sum^k_{a_n=1}gcd(a_1,a_2,a_3,\dots,a_n)\ mod\ 1000000007$$ ### 制約 - $ 2\ \leq\ N\ ......
[数论]GCD&LCM&欧拉函——推柿子+例题
# GCD&LCM&欧拉函——推柿子 ## 一、$\sum_{i = 1}^{n}[\gcd(i,n)=d]$ $\sum_{i = 1}^{n}[\gcd(i,n)=d]$ $=\sum_{i = 1}^{\frac{n}{d}}[\gcd(i,\frac{n}{d})=1]$ $=\phi(\f ......
CF338D GCD Table 题解
# CF338D GCD Table 题解 ## 题目描述 你有一个长度为 $k$ 的数列 $a$ ， 询问是否存在 $x\in[1,n]~~~y\in[1,m]$ 使得 $\forall i~~~ \gcd(x,y+i-1)=a_i$。 ## 解析 我们转换一下可以得到： $$ \forall i ......
Math: GCD LCM
What is the GCD? In mathematics, the greatest common divisor (gcd) of two or more integers, when at least one of them is not zero, is the largest posi ......
Master of GCD（hdu6273）
题面：Problem J. Master of GCDHakase has n numbers in a line. At first, they are all equal to 1. Besides, Hakase is interested in primes.She will choose ......
gcd 证明
## gcd $ gcd(a,b) $ 表示a与b的最大公约数。[here](https://baike.baidu.com/item/%E6%9C%80%E5%A4%A7%E5%85%AC%E7%BA%A6%E6%95%B0/869308) ### gcd 证明 设有 $ gcd(a,b)=d(a ......
数论入门——整除，带余除法，GCD
整除 设 $a,b\in \mathbb{Z},a\ne 0$。如果 $\exists q\in \mathbb{Z}$，使得 $b=a\times q$，那么就说 $b$ 可被 $a$ 整除，记作 $a\mid b$ ；$b$ 不被 $a$ 整除记作 $a\nmid b$ 。 OI Wiki 整除 ......
题解 CF1762D【GCD Queries】
problem 交互题，评测机有一个排列 $p:[int]$，值域是 $[0,n)$，现在可以询问 $2n$ 次 $(x,y)$，评测机回答 $\gcd(p_x,p_y)$，你需要回答 $p$ 中 $0$ 的两个可能的位置。 $\gcd(x,0)=x$，$1\leq n\leq 10^4$。 sol ......
CF338D GCD Table-题解(excrt)
CF338D GCD Table 个人评价：还好 算法 扩展CRT 题面 给了一张$n\times m$的矩阵，第i行j列的权值是gcd(i,j),现在有一个长度为k的序列A，问是否存在(i,j)使得$gcd(i,j+l-1)=a_l(1\leq l\leq k)$ 问题分析 我们将对应行设为x,对 ......
[ABC136E] Max GCD
2023-02-02 题目传送门 翻译 难度&重要性(1~10):4 题目来源 AtCoder 题目算法 数学，贪心 解题思路 记这个数列的和为 $sum$。那么对于每一次操作，$sum$ 的值都不会改变。最后的答案，也一定是 $sum$ 的因数。 那么我们枚举一下 $sum$ 的因数，然后判断一下 ......
高精度四则及GCD运算(二元均是高精度)
原代码出处, 转自HDAWN, 经过部分改写, 包装为结构体, 常数比较大. 测试 输出 大概实际操作 具体 支持四则运算及GCD运算, 重写了istream和ostream和比较运算符. 构造函数既可以, long long, string, 也可以char[] 缺点: 不支持负数, 负数就只能减 ......
gcd相关 2654
如何求取两个数字的最大公约数？ 原理：a和b的最大公约数，也是a和a%b的最大公约数 private int gcd(int a, int b) { //如果b为0，那么直接返回a if(b == 0) return a; //如果a可以被b整除，那么返回b if(a % b == 0) retur ......
gcd(a+c,b+c)!=1,求最小的c
https://ac.nowcoder.com/acm/contest/54877/E 根据更相减损法 gcd(a+c,b+c) = gcd(a-b,a+c),由于a,b已经给出，a-b为固定值。 当a-b为1时，无解 当a-b为0时，若a = 1，则c = 1，否则 c = 0 对于a-b = 其 ......