首页 > 其他分享 >gcd(a, b, c) = gcd(gcd(a, b), c)

gcd(a, b, c) = gcd(gcd(a, b), c)

时间:2023-01-02 21:12:42浏览次数:39  
标签:gcd 勾勾 int 题解 正苦 证明

某一天,我正苦逼的刷题看题解,看到下面的代码

int tmp=0;
		for(int i=1;i<=n;++i){
			scanf("%d",&a[i]);
			tmp=gcd(tmp,a[i]);
		}

​ 我心中一惊:wc,这就能求gcd(a1, a2, a3, ..., an)了?于是,乐于去探索(被数论折磨到精神不正常)的我就想怎么用数学过程推理证明。

​ 我们发现,只要证明gcd(a, b, c) = gcd(gcd(a, b), c)就好了。在纸上勾勾画画半天,突然,灵光一闪,发现能够用分解质因数证明如下:

知识+1:)

标签:gcd,勾勾,int,题解,正苦,证明
From: https://www.cnblogs.com/kekekuli/p/17020512.html

相关文章

  • P2398 GCD SUM——欧拉函数
    此题可以拓展为\(\sum\limits^n_{i=1}\sum\limits^m_{j=1}\gcd(i,j)\)结论是\(\sum\limits^{\min(n,m)}_{d=1}\varphi(d)\lfloor\dfrac{n}{d}\rfloor\lfloor\dfrac{m}{......
  • Trick 5: 关于 GCD 的一些处理方法和性质
    经典的mobius:\(\varepsilon(x)=\sum\limits_{d|x}\mu(d)\)经典的euler:\(x=\sum\limits_{d|x}\varphi(d)\)处理区间问题。如果考虑一段区间的\(\gcd\),那......
  • 容斥原理与gcd的问题
    gcd个数的处理(i,j无限制)P2398GCDSUMi为1-n,j为1-m,求gcd为k的个数代码#include<bits/stdc++.h>usingnamespacestd;#defineintlonglongconstintM=1e5+5;......
  • AtCoder-abc230_g GCD Permutation 容斥
    J-GCDPermutation传送门:J-GCDPermutation知识点:素数筛、容斥定理、gcd题意:长度为n的一个排列a中,求满足\(gcd(i,j)!=1且gcd(a_i,a_j)!=1\)的i,j对数。i,j可以......
  • New Year Concert ( st表 + gcd +二分/ 朴素做法来找思路)
      思路:可以先想朴素的做法来看看找找思路可以发现gcd的元素越多,这个值就会越小,是单调的而且当某个元素不符合时,最优做法:把他设成1e9+7等等数字,这样弄......
  • Codeforces Round #838 (Div. 2) D. GCD Queries
    题意有个长度为n的排列p,[0,1,2,...n-1],你可以进行至多2*n次询问,每次询问两个i,j,返回gcd(pi,pj),让你在规定时间内猜出0在哪两个位置之一思路这是一道交互题,询问的上限是2n......
  • 最大公约数 GCD greatest common divisor
     辗转相除法#include<stdio.h>intmain(void){intm,n,r;scanf("%d%d",&m,&n);if(m<n){m=m^n;n=m^n;......
  • gcd && 素数_legend
    数据处理:(1)gcd(GreatestCommonDivisor):gcd详解:(2)素数(质数)(primenumber): (2.1)判断素数:  (2.1.1)试除法:  (2.1.2)筛选法: (2.2)前N个素数: (2.3)小于等于N的素数......
  • P5435 基于值域预处理的快速 GCD
    P5435基于值域预处理的快速GCD思路也就是将x分解成a*b*c,然后在分别与另一个数求解gcd0-1000之内的gcd是可以直接预处理出来的,因为gcd(a,b)=gcd(a%b,b)(a>b)为......
  • ZROJ237 小T的gcd - 数论 -
    题目链接:http://zhengruioi.com/problem/237题解:首先第一问很简单,如果n个数的gcd为1,答案就是n否则为-1考虑第二问,发现由于lcm是小于等于乘积的,若相等则必然两两互......