数论——约数和倍数

article/2025/7/1 18:18:02

数论——约数和倍数

  • 约数和倍数
    • 试除法求单个数的约数
    • 求每个数的约数集合
    • 唯一分解定理
      • 分解质因数
      • 分解阶乘的质因数
    • 约数个数定理和约数和定理
      • 约数个数定理
      • 约数和定理
    • 约数有关OJ枚举
      • 求一个数的约数之和
      • 求1到n的所有数的约数个数之和
  • 最大公约数gcd和最小公倍数lcm
    • 求gcd的方法
      • 短除法
      • 欧几里得算法
      • 秦九韶算法优化求模运算
      • 二进制算法
      • 唯一分解定理求gcd和lcm
        • 唯一分解定理求gcd
        • 唯一分解定理求lcm
    • 求gcd或lcm相关OJ
      • 蓝桥真题 宝石组合

约数和倍数

如果 a a a 除以 b b b 没有余数,那么 a a a 就是 b b b 的倍数, b b b 就是 a a a 的约数,记作 b ∣ a b|a ba。 约数在其他地方也称因数。

对于一个整数 x x x,若 d d d x x x 的约数,那么 x / d x/d x/d 也是 x x x 的约数。也就是说,除了完全平方数,约数都是成对出现的。因此,可以用试除法求一个整数的所有约数。

试除法求单个数的约数

枚举 1 ∼ x 1 \sim \sqrt{x} 1x 之间的整数,判断是否能整除 x x x

试除法也能求出一个整数的约数个数以及约数总和。

试除法参考:

void get_d(int x, vector<int>&ans){for(int i=1;i<=x/i;i++){//枚举1到sqrt(x)if(x%i==0){ans.push_back(i);if(i!=x/i)ans.push(x/i);}}
}

时间复杂度:

  • 枚举到 n \sqrt{n} n ,因此时间复杂度为 O ( N ) O(\sqrt{N}) O(N )

因此,一个整数 n n n 的约数个数的上限为 2 n 2\sqrt{n} 2n

求每个数的约数集合

如果用试除法分别求每一个数的约数,时间复杂度过高( O ( n n ) O(n\sqrt{n}) O(nn ))。

可以反过来想,对于每个数 d d d [ 1 , n ] [1,n] [1,n] 中以 d d d 为约数的数就是 d d d 的倍数,也就是 d , 2 d , 3 d . . . n d d d, 2d, 3d...\frac{n}{d}d d,2d,3d...dnd。因此可以用倍数法求出 [ 1 , n ] [1,n] [1,n] 每个数的约数集合。

int n;
void get_d(vector<int>&d){for (int i = 1; i <= n; i++) // 枚举所有约数for (int j = 1; j <= n / i; j++) // 约数的倍数d[i * j].push_back(i);
}

时间复杂度:

n n n 倍的调和数,约为 O ( n log ⁡ n ) O(n\log n) O(nlogn)

第1层循环 i = { 1 , 2 , 3 , ⋯ , n } i=\{1,2,3,\cdots,n\} i={1,2,3,,n}时,第2层循环 j j j分别是 { n , n 2 , n 3 , ⋯ , 1 } \{n,\frac{n}{2},\frac{n}{3},\cdots,1\} {n,2n,3n,,1},所以循环总的运行次数是 n ( 1 + 1 2 + 1 3 + ⋯ + 1 n ) n(1+\frac{1}{2}+\frac{1}{3}+\cdots+\frac{1}{n}) n(1+21+31++n1),括号内是个调和级数,当 n n n比价大时,大致等于 ln ⁡ n + γ \ln n+\gamma lnn+γ γ ≈ 0.5772 \gamma\approx 0.5772 γ0.5772是欧拉 - 马歇罗尼常数。所以总的时间复杂度 O ( n ( ln ⁡ n + γ ) ) O(n(\ln n+\gamma)) O(n(lnn+γ)),近似为 O ( n log ⁡ n ) O(n\log n) O(nlogn)

唯一分解定理

算术基本定理又称唯一分解定理

  • 任何一个大于 1 1 1 的自然数 n n n,都可以唯一分解成有限个质数的乘积。
    n = p 1 α 1 × p 2 α 2 × p 3 α 3 … × p k α k n = p_1^{\alpha_1} \times p_2^{\alpha_2} \times p_3^{\alpha_3} \ldots \times p_k^{\alpha_k} n=p1α1×p2α2×p3α3×pkαk
  • 这里 p 1 < p 2 < p 3 < … < p k p_1 < p_2 < p_3 < \ldots < p_k p1<p2<p3<<pk 均为质数,其中指数 α i \alpha_i αi 是正整数。这样的分解称为 n n n 的标准分解式。
  • 求解质数详细见数论——质数和合数及求质数-CSDN博客。

分解质因数

分解质因数就是将一个合数用质因数相乘的形式表示出来,例如 360 = 2 3 × 3 2 × 5 1 360 = 2^3 \times 3^2 \times 5^1 360=23×32×51

试除法分解质因数: n n n 的所有因数中,不会有两个大于 n \sqrt{n} n

因此,枚举 [ 2 , n ] [2, \sqrt{n}] [2,n ] 中所有的数,如果能整除 n n n 就一直除下去。如果最后剩下的数大于 1 1 1,那就是大于 n \sqrt{n} n 的因子。

小优化:如果我们提前打出来一个素数表,枚举所有素数的话,时间复杂度能进一步降低。但求指定范围内的素数本身就消耗时间,在数据量小时直接枚举 [ 2 , n ] [2, \sqrt{n}] [2,n ] 会更合适。

void deprime(int x,vector<int>&ans){for(int i=2;i<=x/i;i++){//枚举到sqrt(x),这里也可以枚举质数int cnt=0;while(x%i==0){x/=i;++cnt;}ans[i]+=cnt;}if(x>1)//有可能它本身就是质数或分解到最后变成质数ans[x]++;
}

分解阶乘的质因数

P2043 质因子分解 - 洛谷

先求阶乘再分解不现实,但可以依次分解 N ! N! N!的每一项,统计次数即可。这题数据量比较小可以直接枚举,但P10495 阶乘分解 - 洛谷就需要先筛选出质数再分解。

#include<bits/stdc++.h>
using namespace std;void ac() {int N; cin >> N;vector<int>num(N + 1, 0);//基于唯一分解定理的试除法for (int i = 2; i <= N; i++) {int x = i;for (int j = 2; j <= i / j; j++) {int cnt = 0;while (x % j == 0) {x /= j;++cnt;}num[j] += cnt;}if (x > 1)num[x]++;}for (int i = 2; i <= N; i++) {if (num[i])cout << i << ' ' << num[i] << '\n';}
}int main() {int T=1;//cin >> T;while (T--)ac();return 0;
}

P10495 阶乘分解 - 洛谷

先求质数,再用质数分解阶乘,否则最后一个样例会超时。

还有一种正难则反的思路:对每个质数或这个质数的若干次幂,统计有多少个数包含它。

例如 n = 10 n=10 n=10,对质数2, ⌊ 10 2 ⌋ = 5 \lfloor\frac{10}{2}\rfloor=5 210=5 ⌊ 10 2 2 ⌋ = 2 \lfloor\frac{10}{2^2}\rfloor=2 2210=2 ⌊ 10 2 3 ⌋ = 1 \lfloor\frac{10}{2^3}\rfloor=1 2310=1,所以 10 ! 10! 10!的质因数次幂之一是 2 8 2^8 28。这种方法可以理解为以 2 x 2^x 2x个数为一组,其中必定有1个数是 2 x 2^x 2x乘多少得到的合数。

例如{1,2,3,4}{5,6,7,8},都至少有2个是 2 2 2^2 22乘谁构成的合数,正好等于 ⌊ 10 2 2 ⌋ \lfloor\frac{10}{2^{2}}\rfloor 2210

#include<bits/stdc++.h>
using namespace std;vector<int>p;
vector<bool>vis(1e6 + 1, 0);//欧拉筛
void prim() {int n = 1e6;for (int i = 2; i <= n; i++) {if (!vis[i])p.push_back(i);for (size_t j = 0; 1ull * i * p[j] <= n; j++) {vis[i * p[j]] = 1;if (i % p[j] == 0)break;}}
}//优化唯一分解定理
void ac() {int N; cin >> N;vector<int>num(N + 1, 0);for (int i = 2; i <= N; i++) {int x = i;for (int j = 0; p[j] * p[j] <= x; j++) {//质数的平方不能超过xint cnt = 0;while (x % p[j] == 0) {x /= p[j];++cnt;}num[p[j]] += cnt;}if (x > 1)num[x]++;}for (size_t i = 2; i < num.size(); i++)if (num[i])cout << i << ' ' << num[i] << '\n';
}//正难则反
typedef unsigned long long ULL;
void ac2() {int N; cin >> N;for (size_t i = 0, cnt; i < p.size() && p[i] <= N; i++) {//枚举质数cnt = 0;for (ULL j = p[i]; j <= N; j *= p[i])//枚举质数次幂cnt += N / j;cout << p[i] << ' ' << cnt << endl;}
}int main() {int T = 1;prim();//cin >> T;while (T--)//ac();//优化唯一分解定理ac2();//正难则反return 0;
}

约数个数定理和约数和定理

这2个定理最常用的是结合质数筛(欧拉筛)配合积性函数,打表约数个数以及约数和,整体时间复杂度是 O ( n ) O(n) O(n)

约数个数定理

由唯一分解定理得: n = p 1 α 1 × p 2 α 2 × p 3 α 3 … × p k α k n = p_1^{\alpha_1} \times p_2^{\alpha_2} \times p_3^{\alpha_3} \ldots \times p_k^{\alpha_k} n=p1α1×p2α2×p3α3×pkαk

若用 d d d 表示某一个数约数的个数,那么有:
d ( n ) = ( α 1 + 1 ) ( α 2 + 1 ) ⋯ ( α n + 1 ) = ∏ i = 1 k ( α i + 1 ) d(n) = (\alpha_1 + 1)(\alpha_2 + 1)\cdots(\alpha_n + 1)=\prod_{i=1}^k (\alpha_i + 1) d(n)=(α1+1)(α2+1)(αn+1)=i=1k(αi+1)

即每个质因数幂都有 { 0 , 1 , 2 , ⋯ , α i } \{0,1,2,\cdots,\alpha_i\} {0,1,2,,αi} α i + 1 \alpha_i+1 αi+1种情况,根据乘法原理一共有 ∏ i = 1 k ( α i + 1 ) \prod_{i=1}^k (\alpha_i + 1) i=1k(αi+1)种情况。

例如12的约数{1,2,3,4,6,12},且 12 = 2 2 × 3 12=2^{2}\times 3 12=22×3,约数个数正好是 ( 2 + 1 ) ( 1 + 1 ) = 6 (2+1)(1+1)=6 (2+1)(1+1)=6

所以试除法求单个数的约数个数

  • 第一种方式:枚举 1 ∼ x 1 \sim \sqrt{x} 1x 之间的整数,看哪些数能被 x x x整除。
  • 第二种方式:在借助唯一分解定理分解质因数的过程中,利用约数个数定理的公式可以直接计算出某个数的约数个数。

约数和定理

由唯一分解定理得: n = p 1 α 1 × p 2 α 2 × p 3 α 3 … × p k α k n = p_1^{\alpha_1} \times p_2^{\alpha_2} \times p_3^{\alpha_3} \ldots \times p_k^{\alpha_k} n=p1α1×p2α2×p3α3×pkαk

若用 f f f 表示某一个数约数和,那么有: f ( n ) = ∏ i = 1 k ∑ j = 0 α i p i j f(n) = \prod_{i=1}^k \sum_{j=0}^{\alpha_i} p_i^{j} f(n)=i=1kj=0αipij

例如 12 = 2 2 × 3 12=2^{2}\times 3 12=22×3 f ( 12 ) = ( 2 0 + 2 1 + 2 2 ) ( 1 + 3 1 ) = 28 f(12)=(2^0+2^1+2^2)(1+3^1)=28 f(12)=(20+21+22)(1+31)=28

所以试除法求单个数的约数之和

  • 第一种方式:枚举 1 ∼ x 1 \sim \sqrt{x} 1x 之间的整数,将能被 x x x整除的约数加起来。

例如 1 + 12 + 2 + 6 + 3 + 4 = 28 1+12+2+6+3+4=28 1+12+2+6+3+4=28

  • 第二种方式:在借助唯一分解定理分解质因数的过程中,利用约束和定理的公式可以直接计算出某个数的约数总数。

约数有关OJ枚举

分解阶乘的质因数:

  1. P2043 质因子分解 - 洛谷
  2. P10495 阶乘分解 - 洛谷

上文有描述,这里不再重复。

求一个数的约数之和

约数之和

  1. 试除法枚举。
  2. 约数和定理。
#include<bits/stdc++.h>
using namespace std;typedef long long LL;
void ac() {//试除法枚举LL n;cin >> n;LL sum = 0;for (LL i = 1; i <= n / i; i += 1) {if (n % i == 0) {sum += i;if (i != n / i)sum += n / i;}}cout << sum;
}void ac2() {//约数和定理LL n; cin >> n;vector<int>p(n + 1, 0);//分解质因数for (LL i = 2; i <= n / i; i += 1) {int cnt = 0;while (n % i == 0) {++cnt;n /= i;}p[i] += cnt;}if (n > 1)p[n]++;//约数和定理LL sum = 0,ans=1;for (int i = 2,pp=0; i <= n;i++) {if (p[i]) {pp = i;sum += 1;//0次方for (int j = 1; j <= p[i]; j++) {sum += pp;pp *= i;}ans *= sum;sum = 0;}}cout << ans;
}int main() {int T = 1;//cin >> T;while (T--)//ac();ac2();return 0;
}

求1到n的所有数的约数个数之和

约数个数的和

这题数据量很大( 10 8 10^8 108),开数组很容易内存超限。

但可以通过正难则反的思想投机取巧:对每个数 x x x,在 [ 1 , n ] [1,n] [1,n]中,可以分成 n x \frac{n}{x} xn组,每组有1个数,它的约数之一是 x x x

举个例子, n = 20 n=20 n=20 x = 5 x=5 x=5,此时 [ 1 , 20 ] [1,20] [1,20]可分成4组:{1,2,3,4,5}{6,7,8,9,10}{11,12,13,14,15}{16,17,18,19,20},其中{5,10,15,20}的约数都有1个5,正好是4个。

所以这题要求的约数个数之和是 Σ i = 1 n n i \Sigma_{i=1}^{n}\frac{n}{i} Σi=1nin

#include<bits/stdc++.h>
using namespace std;void ac() {int n; cin >> n;int cnt = 0;for (int i = 1; i <= n / 2; i++) {cnt += n / i;}//后半部分的n/i全是1,直接除不划算,所以直接通过公式求和即可cout << cnt + n - n / 2;
}int main() {int T = 1;//cin >> T;while (T--)ac();return 0;
}

最大公约数gcd和最小公倍数lcm

这2个概念都是基于2个或2个以上的数。

【最大公约数和最小公倍数】

最大公约数(Greatest Common Divisor),常缩写为 gcd。有的资料也称最大公因数。

  • 一组整数的公约数,是指同时是这组数中每一个数的约数的数。例如{6,8,12}的公约数有1、2。
  • 一组整数的最大公约数,是指所有公约数里面最大的一个。 例如{12,8,16}的最大公约数是4。

最小公倍数(Least Common Multiple),常缩写为 lcm。

  • 一组整数的公倍数,是指同时是这组数中每一个数的倍数的数
  • 一组整数的最小公倍数,是指所有正的公倍数里面,最小的一个数。

求两个数的 gcd 与 lcm 时,有如下性质:

  • 对于两个数 a a a b b b g c d ( a , b ) × l c m ( a , b ) = a × b \mathrm{gcd(a, b)} \times \mathrm{lcm(a, b)} = a \times b gcd(a,b)×lcm(a,b)=a×b。也就是最大公约数乘以最小公倍数等于两个数的乘积。

因此,一般先求最大公约数,然后用这个性质求最小公倍数。

求gcd的方法

求gcd可通过模板题[B3736 信息与未来 2018] 最大公约数 - 洛谷进行验证。

短除法

这是最古老的求 gcd 的方法。原理是枚举 a a a b b b 可能的公约数并不断缩小 a a a b b b 的值,当 a a a b b b 再无法枚举公约数时,将所有枚举过的公约数和最后的 a a a b b b 作乘,即为 g c d ( a , b ) \mathrm{gcd(a,b)} gcd(a,b)
请添加图片描述

这个方法一般不用代码实现,更多用于平时验算时使用。

欧几里得算法

在数论里很重要的3个算法:快速幂算法,欧几里得算法,(质数的)线性筛算法。这3个算法算是数论中很基础的算法,应用会非常多。

欧几里得算法也称辗转相除法,可以求出两个整数的最大公约数。

算法流程:

a > b a > b a>b

  • 如果 b b b a a a 的约数,那么 b b b 就是两者的最大公约数。
  • 如果 b b b 不是 a a a 的约数,那么 g c d ( a , b ) = g c d ( b , a m o d b ) \mathrm{gcd}(a, b) = \mathrm{gcd}(b, a \bmod b) gcd(a,b)=gcd(b,amodb)

因为 a m o d b a \bmod b amodb 会不断减小,因此可以用递归或循环进行求解。

例如求 g c d ( 8 , 14 ) \mathrm{gcd}(8,14) gcd(8,14)
g c d ( 8 , 14 ) → g c d ( 14 , 8 ) → g c d ( 8 , 6 ) → g c d ( 6 , 2 ) → g c d ( 2 , 0 ) → 2 \mathrm{gcd}(8,14)\rightarrow \mathrm{gcd}(14,8)\rightarrow \mathrm{gcd}(8,6)\rightarrow \mathrm{gcd}(6,2)\rightarrow \mathrm{gcd}(2,0)\rightarrow 2 gcd(8,14)gcd(14,8)gcd(8,6)gcd(6,2)gcd(2,0)2

非递归算法实现:

int gcd(int a, int b) {//int可更换成long long或__int128int r = a % b;while (r) {//当r为0时,说明此时的b是最开始的a和b的约数a = b;b = r;r = a % b;}return b;
}

递归算法实现:

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

证明这个算法的正确性,只需证明 g c d ( a , b ) = g c d ( b , a m o d b ) \mathrm{gcd}(a, b) = \mathrm{gcd}(b, a \bmod b) gcd(a,b)=gcd(b,amodb)即可:

首先是证明这个结论: d ∣ a d|a da d ∣ b d|b db可得 d ∣ ( a x + b y ) d|(ax+by) d(ax+by)。例如 2 ∣ 12 2|12 2∣12 2 ∣ 10 2|10 2∣10 2 ∣ ( 12 x + 10 y ) → 2 × ( 6 x + 10 y ) 2|(12x+10y)\rightarrow 2\times (6x+10y) 2∣(12x+10y)2×(6x+10y),无论 x x x y y y有多大, a x ax ax b y by by都能提取出约数 d d d

d ∣ ( a x + b y ) = d ∣ ( a d x + b d y ) d|(ax+by)=d|(\frac{a}{d}x+\frac{b}{d}y) d(ax+by)=d(dax+dby)。这个等式后续用于证明欧几里得算法。

已知 a % b = c a\%b=c a%b=c a ÷ b = k ⋯ c a\div b=k\cdots c a÷b=kc。所以 k b + c = a kb+c=a kb+c=a c = a − k b ( k = a b ) c=a-kb(k=\frac{a}{b}) c=akb(k=ba)

因此 g c d ( b , a m o d b ) = g c d ( b , a − k b ) = d \mathrm{gcd}(b, a \bmod b)=\mathrm{gcd}(b, a-kb)=d gcd(b,amodb)=gcd(b,akb)=d

证明 g c d ( a , b ) = g c d ( b , a m o d b ) \mathrm{gcd}(a, b) = \mathrm{gcd}(b, a \bmod b) gcd(a,b)=gcd(b,amodb),先证明左边等于右边:

假设 g c d ( a , b ) = d \mathrm{gcd}(a,b)=d gcd(a,b)=d,则 g c d ( a , b ) → d ∣ a , d ∣ b → d ∣ ( 1 a − k b ) \mathrm{gcd}(a,b)\rightarrow d|a,\ d|b\rightarrow \ d|(1a-kb) gcd(a,b)da, db d(1akb)
d ∣ ( a − 1 k b ) d|(a-1kb) d(a1kb),故 d ∣ b , d ∣ a m o d b d|b,\ d|a\bmod b db, damodb,因此 g c d ( a , b ) → g c d ( b , a m o d b ) \mathrm{gcd}(a,b)\rightarrow \mathrm{gcd}(b,a\bmod b) gcd(a,b)gcd(b,amodb)

后证明右边等于左边:

d ∣ b , d ∣ ( a − k b ) → d ∣ ( k b + a − k b ) = d ∣ a d|b,\ d|(a-kb)\rightarrow d|(kb+a-kb)=d|a db, d(akb)d(kb+akb)=da
所以 d ∣ b , d ∣ ( a − k b ) = d ∣ b , d ∣ a → g c d ( b , a m o d b ) = g c d ( a , b ) d|b,\ d|(a-kb)=d|b, d|a\rightarrow \mathrm{gcd}(b,a\bmod b)=\mathrm{gcd}(a,b) db, d(akb)=db,dagcd(b,amodb)=gcd(a,b)

证明完毕。

这个算法的时间复杂度是 O ( log ⁡ min ⁡ ( a , b ) ) O(\log \min(a,b)) O(logmin(a,b))

[B3736 信息与未来 2018] 最大公约数 - 洛谷参考程序:

#include<bits/stdc++.h>
using namespace std;int gcd(int a, int b) {//int可更换成long long或__int128int r = a % b;while (r) {//当r为0时,说明b是a的约数a = b;b = r;r = a % b;}return b;
}int main() {int a, b, c;cin >> a >> b >> c;cout << gcd(gcd(a,b), c);return 0;
}

还有一种更相减损术,但平时用的不是很多,这里就不举例。

秦九韶算法优化求模运算

小红的 gcd

这个题要求gcd的数,长度太大无法使用c语言自带的数据结构去存储,因此需要用字符串去存储,也就是说要通过高精度计算去求gcd。

但用传统的欧几里得算法,在这个题会超时。

秦九韶算法是一种将一元 n n n 次多项式的求值问题转化为 n n n 个一次式的算法。其大大简化了计算过程,即使在现代,利用计算机解决多项式的求值问题时,秦九韶算法依然是最优的算法(不知道现在是否有更好的算法)。

一个 n n n 次多项式:
f ( x ) = a n x n + a n − 1 x n − 1 + a n − 2 x n − 2 + ⋯ + a 1 x 1 + a 0 x 0 f(x) = a_n x^n + a_{n-1} x^{n-1} + a_{n-2} x^{n-2} + \cdots + a_1 x^1 + a_0 x^0 f(x)=anxn+an1xn1+an2xn2++a1x1+a0x0
可以改写成:

f ( x ) = ( a n x n − 1 + a n − 1 x n − 2 + a n − 2 x n − 3 + ⋯ + a 1 ) x + a 0 = ( ( a n x n − 2 + a n − 1 x n − 3 + a n − 2 x n − 4 + ⋯ + a 2 ) x + a 1 ) x + a 0 ⋅ ⋅ ⋅ = ( ⋅ ( ( a n x + a n − 1 ) x + a n − 2 ) x + ⋯ + a 2 ) x + a 1 ) x + a 0 f(x) = (a_n x^{n-1} + a_{n-1} x^{n-2} + a_{n-2} x^{n-3} + \cdots + a_1)x + a_0 \\ = ((a_n x^{n-2} + a_{n-1} x^{n-3} + a_{n-2} x^{n-4} + \cdots + a_2)x + a_1)x + a_0 \\ \quad \cdot \\ \quad \cdot \\ \quad \cdot \\ = (\cdot((a_n x + a_{n-1})x + a_{n-2})x + \cdots + a_2)x + a_1)x + a_0 f(x)=(anxn1+an1xn2+an2xn3++a1)x+a0=((anxn2+an1xn3+an2xn4++a2)x+a1)x+a0=(((anx+an1)x+an2)x++a2)x+a1)x+a0

例如:对于一个整数 987654321,可以拆成:
( ( ( ( ( ( 9 × 10 + 8 ) × 10 + 7 ) × 10 + 6 ) × 10 + 5 ) × 10 + 4 ) × 10 + 3 ) × 10 + 2 ) × 10 + 1 ((((((9 \times 10 + 8) \times 10 + 7) \times 10 + 6) \times 10 + 5) \times 10 + 4) \times 10 + 3) \times 10 + 2) \times 10 + 1 ((((((9×10+8)×10+7)×10+6)×10+5)×10+4)×10+3)×10+2)×10+1

这个算法可以在 O ( n ) O(n) O(n)的时间复杂度内求一元 n n n 次多项式的值。

对于高精度的数取模,就可以分阶段取模。因为方程只涉及加法和乘法,所以可以在计算一个括号内的值时顺便取模。例如 x = ( ( 9 × 10 ) + 8 ) m o d M x=((9\times 10)+8)\bmod M x=((9×10)+8)modM,这个值可以直接参与后续的运算: ( 10 x + 7 ) m o d M (10x+7)\bmod M (10x+7)modM等。

对小红的 gcd需要秦九韶算法配合欧几里得算法来求。

#include<bits/stdc++.h>
using namespace std;
typedef long long LL;LL gcd(string& aa, LL b) {LL a = 0,r=0;for (auto& x : aa) {//先通过秦九韶算法求aa%ba = a * 10 + x - '0';a %= b;}//然后就是一般的欧几里得算法r = a % b;while (r) {a = b; b = r; r = a % b;}return b;
}int main() {string a;LL b;cin >> a >> b;cout << gcd(a, b);return 0;
}

二进制算法

因为高精度除法(取模)不容易实现,需要做高精度运算时,可以考虑用二进制算法。

a = b a = b a=b gcd ( a , b ) = a \text{gcd}(a, b) = a gcd(a,b)=a;否则,分情况讨论:

  1. a a a b b b 均为偶数, gcd ( a , b ) = 2 × gcd ( a / 2 , b / 2 ) \text{gcd}(a, b) = 2 \times \text{gcd}(a/2, b/2) gcd(a,b)=2×gcd(a/2,b/2)

  2. a a a 为偶数 b b b 为奇数, gcd ( a , b ) = gcd ( a / 2 , b ) \text{gcd}(a, b) = \text{gcd}(a/2, b) gcd(a,b)=gcd(a/2,b)

  3. a a a 为奇数 b b b 为偶数, gcd ( a , b ) = gcd ( a , b / 2 ) \text{gcd}(a, b) = \text{gcd}(a, b/2) gcd(a,b)=gcd(a,b/2)

  4. a a a b b b 均为奇数, gcd ( a , b ) = gcd ( abs ( a − b ) , min ( a , b ) ) \text{gcd}(a, b) = \text{gcd}(\text{abs}(a - b), \text{min}(a,b)) gcd(a,b)=gcd(abs(ab),min(a,b))

  5. b = 0 b=0 b=0,则 a a a是最终解。 a = 0 a=0 a=0,则 b b b是最终解。

循环实现:

int gcd2(int a, int b) {//int 可换成别的大整数类int ans = 1;while (a > 0 && b > 0) {if (a % 2 == 0 && b % 2 == 0) {ans *= 2;a /= 2;b /= 2;}else if (a % 2 == 0)a /= 2;else if (b % 2 == 0)b /= 2;else if (a > b)a -= b;elseb -= a;}return ans * (a <= 0 ? b : a);
}

递归实现:

int gcd(int a, int b) {if (a <= 0)//终止条件return b;if (b <= 0)return a;if (a % 2 == 0 && b % 2 == 0)return 2 * gcd(a / 2, b / 2);else if (a % 2 == 0)return gcd(a / 2, b);else if (b % 2 == 0)return gcd(a, b / 2);elsereturn a > b ? gcd(a - b, b) : gcd(b - a, a);//避免负数问题
}

但绝大部分情况是数据量偏小,而且二进制并不好处理2个数互质的情况,因此一般不用。

唯一分解定理求gcd和lcm

唯一分解定理还在追我(bushi)。

唯一分解定理求gcd

可以先分解2个因数,再求gcd。

即求 g c d ( a , b ) \mathrm{gcd}(a,b) gcd(a,b),可以先根据唯一分解定理将 a a a b b b分解:

a = p 1 α 1 × p 2 α 2 × p 3 α 3 … × p k α k a=p_1^{\alpha_1} \times p_2^{\alpha_2} \times p_3^{\alpha_3} \ldots \times p_k^{\alpha_k} a=p1α1×p2α2×p3α3×pkαk

b = p 1 β 1 × p 2 β 2 × p 3 β 3 … × p k β k b=p_1^{\beta_1} \times p_2^{\beta_2} \times p_3^{\beta_3} \ldots \times p_k^{\beta_k} b=p1β1×p2β2×p3β3×pkβk

gcd ⁡ ( a , b ) = p 1 min ⁡ ( α 1 , β 1 ) × p 2 min ⁡ ( α 2 , β 2 ) × ⋯ × p k min ⁡ ( α k , β k ) \gcd(a,b)=p_1^{\min(\alpha_1,\beta_1)}\times p_2^{\min(\alpha_2,\beta_2)}\times\cdots \times p_k^{\min(\alpha_k,\beta_k)} gcd(a,b)=p1min(α1,β1)×p2min(α2,β2)××pkmin(αk,βk)

例如 g c d ( 18 , 12 ) = 2 m i n ( 1 , 2 ) × 3 m i n ( 2 , 1 ) = 2 × 3 = 6 \mathrm{gcd}(18,12)=2^{\mathrm{min}(1,2)}\times 3^{\mathrm{min}(2,1)}=2\times 3=6 gcd(18,12)=2min(1,2)×3min(2,1)=2×3=6

这个公式可以这样理解: g c d ( a , b ) \mathrm{gcd}(a,b) gcd(a,b)是能同时被 a a a b b b整除的最大整数,所以 g c d ( a , b ) \mathrm{gcd}(a,b) gcd(a,b)必须包含 a a a b b b公有的质因数也就是 p i x p_i^x pix

取最小值是因为若 x > α 1 x>\alpha_1 x>α1,则最后的 g c d ( a , b ) \mathrm{gcd}(a,b) gcd(a,b)不能被 a a a整除,同理若 x > β 1 x>\beta_1 x>β1,则最后的 g c d ( a , b ) \mathrm{gcd}(a,b) gcd(a,b)不能被 b b b整除。

这个公式还能推广到若干个数的情况:

g c d ( a 1 , a 2 , … , a n ) = ∏ p p i min ⁡ ( α 1 , α 2 , … , α n ) \mathrm{gcd}(a_1,a_2,\ldots,a_n)=\prod_p p_i^{\min(\alpha_1,\alpha_2,\ldots,\alpha_n)} gcd(a1,a2,,an)=ppimin(α1,α2,,αn)

例如 g c d ( 24 , 36 , 60 ) \mathrm{gcd}(24,36,60) gcd(24,36,60),根据唯一分解定理,

24 = 2 3 × 3 1 24=2^3\times 3^1 24=23×31

36 = 2 2 × 3 2 36=2^2\times 3^2 36=22×32

60 = 2 2 × 3 1 × 5 1 60=2^2\times 3^1\times 5^1 60=22×31×51

所以 g c d ( 24 , 36 , 60 ) = 2 m i n ( 3 , 2 , 2 ) × 3 m i n ( 1 , 2 , 1 ) × 5 m i n ( 0 , 0 , 1 ) = 2 2 × 3 1 × 5 0 = 12 \mathrm{gcd}(24,36,60)=2^{\mathrm{min}(3,2,2)}\times 3^{\mathrm{min}(1,2,1)}\times 5^{\mathrm{min}(0,0,1)}=2^2\times 3^1\times 5^0=12 gcd(24,36,60)=2min(3,2,2)×3min(1,2,1)×5min(0,0,1)=22×31×50=12

唯一分解定理求lcm

即求 l c m ( a , b ) \mathrm{lcm(a,b)} lcm(a,b),可以先根据唯一分解定理将 a a a b b b分解:

a = p 1 α 1 × p 2 α 2 × p 3 α 3 … × p k α k a=p_1^{\alpha_1} \times p_2^{\alpha_2} \times p_3^{\alpha_3} \ldots \times p_k^{\alpha_k} a=p1α1×p2α2×p3α3×pkαk

b = p 1 β 1 × p 2 β 2 × p 3 β 3 … × p k β k b=p_1^{\beta_1} \times p_2^{\beta_2} \times p_3^{\beta_3} \ldots \times p_k^{\beta_k} b=p1β1×p2β2×p3β3×pkβk

l c m ( a , b ) = p 1 max ⁡ ( α 1 , β 1 ) × p 2 max ⁡ ( α 2 , β 2 ) × ⋯ × p k max ⁡ ( α k , β k ) \mathrm{lcm(a,b)}=p_1^{\max(\alpha_1,\beta_1)}\times p_2^{\max(\alpha_2,\beta_2)}\times\cdots \times p_k^{\max(\alpha_k,\beta_k)} lcm(a,b)=p1max(α1,β1)×p2max(α2,β2)××pkmax(αk,βk)

例如 l c m ( 12 , 18 ) = 2 m a x ( 1 , 2 ) × 3 m a x ( 2 , 1 ) = 2 2 × 3 9 = 36 \mathrm{lcm(12,18)}=2^{\mathrm{max}(1,2)}\times 3^{\mathrm{max}(2,1)}=2^2\times 3^9=36 lcm(12,18)=2max(1,2)×3max(2,1)=22×39=36

这个公式可以这样理解: l c m ( a , b ) \mathrm{lcm(a,b)} lcm(a,b)是能同时 a a a b b b被整除的最小整数,所以 l c m ( a , b ) \mathrm{lcm(a,b)} lcm(a,b)必须包含 a a a b b b公有的质因数也就是 p i x p_i^x pix

x x x α i \alpha_i αi β i \beta_i βi都小时, l c m ( a , b ) \mathrm{lcm(a,b)} lcm(a,b)就不能被 a a a b b b整除,因此取 m a x \mathrm{max} max

这个公式同样能推广:

l c m ( a 1 , a 2 , … , a n ) = ∏ p p i max ⁡ ( α 1 , α 2 , … , α n ) \mathrm{lcm}(a_1,a_2,\ldots,a_n)=\prod_p p_i^{\max(\alpha_1,\alpha_2,\ldots,\alpha_n)} lcm(a1,a2,,an)=ppimax(α1,α2,,αn)

例如 l c m ( 8 , 12 , 15 ) = 2 m a x ( 3 , 2 , 0 ) × 3 m a x ( 0 , 1 , 1 ) × 5 m a x ( 0 , 0 , 1 ) = 2 3 × 3 1 × 5 1 = 120 \mathrm{lcm(8,12,15)}=2^{\mathrm{max(3,2,0)}}\times 3^{\mathrm{max(0,1,1)}}\times5^{\mathrm{max(0,0,1)}}=2^3\times 3^1\times 5^1=120 lcm(8,12,15)=2max(3,2,0)×3max(0,1,1)×5max(0,0,1)=23×31×51=120

求gcd或lcm相关OJ

模板题:[B3736 信息与未来 2018] 最大公约数 - 洛谷

秦九韶算法优化:小红的 gcd

这2个在上文有说明,这里不再重复。

蓝桥真题 宝石组合

[P10426 蓝桥杯 2024 省 B] 宝石组合 - 洛谷

首先是这个很唬人的公式。遇到这种公式一般都可以分解,或用于代入枚举。

S = H a H b H c ⋅ L C M ( H a , H b , H c ) L C M ( H a , H b ) ⋅ L C M ( H a , H c ) ⋅ L C M ( H b , H c ) S = H_aH_bH_c \cdot \frac{\mathrm{LCM}(H_a,H_b,H_c)}{\mathrm{LCM}(H_a,H_b) \cdot \mathrm{LCM}(H_a,H_c) \cdot \mathrm{LCM}(H_b,H_c)} S=HaHbHcLCM(Ha,Hb)LCM(Ha,Hc)LCM(Hb,Hc)LCM(Ha,Hb,Hc)

根据唯一分解定理得到:

H a = ∏ p p i a i H_a=\prod_{p}p_i^{a_i} Ha=ppiai H b = ∏ p p i b i H_b=\prod_{p}p_i^{b_i} Hb=ppibi H c = ∏ p p i c i H_c=\prod_{p}p_i^{c_i} Hc=ppici

配合唯一分解定理推导的 gcd \text{gcd} gcd lcm \text{lcm} lcm的公式,得:

S = ∏ p p i a i + b i + c i + m a x ( a i , b i , c i ) − m a x ( a i , b i ) − m a x ( a i , c i ) − m a x ( b i , c i ) S=\prod_{p}p_i^{a_i+b_i+c_i+\mathrm{max(a_i,b_i,c_i)}-\mathrm{max(a_i,b_i)}-\mathrm{max(a_i,c_i)}-\mathrm{max(b_i,c_i)}} S=ppiai+bi+ci+max(ai,bi,ci)max(ai,bi)max(ai,ci)max(bi,ci),这里 a i a_i ai b i b_i bi c i c_i ci分别表示质因数 p i p_i pi的指数。

因为未知数有3个,所以这里能做的也只有假设。假设 a i ≤ b i ≤ c i a_i\leq b_i\leq c_i aibici a i ≥ b i ≥ c i a_i\geq b_i\geq c_i aibici也行),则 m a x ( a i , b i , c i ) = a i \mathrm{max(a_i,b_i,c_i)}=a_i max(ai,bi,ci)=ai

此时公式简化为 S = ∏ p p i a i + b i + c i + c i − b i − c i − c i = ∏ p p i a i = ∏ p p i m i n ( a i , b i , c i ) = g c d ( a , b , c ) S=\prod_{p}p_i^{a_i+b_i+c_i+c_i-b_i-c_i-c_i}=\prod_{p}p_i^{a_i}=\prod_{p}p_i^{\mathrm{min(a_i,b_i,c_i)}}=\mathrm{gcd(a,b,c)} S=ppiai+bi+ci+cibicici=ppiai=ppimin(ai,bi,ci)=gcd(a,b,c)

因此这个题就变成了选3个宝石,这些宝石的最小公倍数最大。

所以就有了一种特别暴力的解法:创建一个二维数组g[i],表示以i为约数的数的集合。之后枚举所有宝石的数值,根据它们的约数对号入座。最后逆向枚举所有约数,拥有3个成员的那个约数的前3个成员就是答案。

例如样例:

5
1 2 3 4 9

按照约数对号入座:

1:[1,2,3,4,9]
2:[2,4]
3:[3,9]
4:[4]
...
9:[9]

很明显只有1符合要求,因此答案就是{1,2,3}

总的时间复杂度是 O ( n n ) O(n\sqrt{n}) O(nn ),总的数据量是 10 5 10^5 105,程序的运行次数的数量级为 10 7 10^7 107,可以在1秒内实现。

#include<bits/stdc++.h>
using namespace std;void ac() {int n;cin >> n;vector<int>a(n, 0);for (auto& x : a)cin >> x;sort(a.begin(), a.end());vector<vector<int> >g(a[a.size()-1] + 1);for (auto& x : a) {//对每个数,按照各自有的约数对号入座int sq = sqrt(x);for (int i = 1; i <= sq; i++) {if (x % i == 0) {g[i].push_back(x);if (x / i != i)g[x / i].push_back(x);}}}//逆序枚举所有约数,只要找到第1个有3个以上的成员,则前3个就是答案for (int i = a[a.size()-1]; i > 0; i--) {if (g[i].size() >= 3) {cout << g[i][0] << ' ' << g[i][1] << ' ' << g[i][2];return;}}
}int main() {int T = 1;//cin >> T;while (T--)ac();return 0;
}

http://www.hkcw.cn/article/EnvSUjxOSR.shtml

相关文章

线程池详细解析(二)

本章我们将继续讲述线程池的源码解析给&#xff0c;上一章我们了解了一下Worker内部类这个用作包装线程池的工作线程的内部类。本章我们看看他的核心方法 Worker(Runnable var2) {this.setState(-1);this.firstTask var2;this.thread ThreadPoolExecutor.this.getThreadFacto…

docker运行程序Killed异常排查

问题描述 我最近开发了一个C 多线程程序&#xff0c;测试没有问题&#xff0c;封装docker测试也没有问题&#xff0c;然后提交给客户了&#xff0c;然后在他那边测试有问题&#xff0c;不定时、不定位置异常中断&#xff0c;以前一直认为只要封装了docker就万事大吉&#xff0…

Linux--进程概念

1.基本概念与基本操作 • 课本概念&#xff1a;程序的⼀个执⾏实例&#xff0c;正在执⾏的程序等 • 内核观点&#xff1a;担当分配系统资源&#xff08;CPU时间&#xff0c;内存&#xff09;的实体。 2 描述进程-PCB 基本概念 • 进程信息被放在⼀个叫做进程控制块的数据…

铁电液晶破局 VR/AR:10000PPI 重构元宇宙显示体验

一、VR/AR 沉浸感困境&#xff1a;传统显示技术的天花板在哪&#xff1f; &#xff08;一&#xff09;纱窗效应与眩晕感&#xff1a;近眼显示的双重枷锁 当用户戴上 VR 头显&#xff0c;眼前像素网格形成的 “纱窗效应” 瞬间打破沉浸感。传统液晶 500-600PPI 的像素密度&…

edge进行重置设置之后,网页无法访问(显示连接不是专用连接)

问题&#xff1a; edge进行重置设置之后&#xff0c;网页无法访问&#xff08;显示连接不是专用连接&#xff09;&#xff0c;如下图&#xff1a; 解决方法&#xff1a; 调整键盘为英文输入状态&#xff0c;刷新一下页面&#xff0c;鼠标点击页面任意位置&#xff08;不要点击到…

sql注入补充——get注入

Sql注入 Mysql中的information_schema库 用于存储数据库元信息&#xff0c;包含了数据库、表、列、索引等结构化信息。 特点&#xff1a; 只读性 标准化&#xff1a;它是sql标准的一部分&#xff0c;适用于多种数据库系统 动态生成&#xff1a;数据是动态生成的&#xff…

eBay关键词搜索API开发指南

一、接口概述 eBay的Finding API提供findItemsByKeywords方法&#xff0c;支持通过关键词检索商品列表。该接口采用REST架构&#xff0c;返回标准JSON/XML格式数据&#xff0c;日均调用限额5000次&#xff08;生产环境需申请提升配额&#xff09;。 二、核心参数说明 必需参…

<6>, 界面优化

目录 一&#xff0c;QSS 1&#xff0c;背景介绍 2&#xff0c;基本语法 3&#xff0c;设置方式 &#xff08;1&#xff09;指定控件样式设置 &#xff08;2&#xff09;全局样式设置 &#xff08;3&#xff09;从文件加载样式表 &#xff08;4&#xff09;使用 Qt Desig…

截图工具 Snipaste V2.10.7(2025.06.2更新)

—————【下 载 地 址】——————— 【​本章下载一】&#xff1a;https://pan.xunlei.com/s/VORklK9hcuoI6n_qgx25jSq2A1?pwde7bi# 【​本章下载二】&#xff1a;https://pan.quark.cn/s/7c62f8f86735 【百款黑科技】&#xff1a;https://ucnygalh6wle.feishu.cn/wiki/…

Docker安装Redis集群(3主3从+动态扩容、缩容)保姆级教程含踩坑及安装中遇到的问题解决

前言 部署集群前&#xff0c;我们需要先掌握Redis分布式存储的核心算法。了解这些算法能帮助我们在实际工作中做出合理选择&#xff0c;同时清晰认识各方案的优缺点。 一、分布式存储算法 我们通过一道大厂面试题来进行阐述。 如下&#xff1a;1-2亿条数据需要缓存&#xff…

Altium Disigner(16.1)学习-元器件封装

一、元器件封装 封装就是给画的原理图所有的器件的外形描述出来&#xff08;几个引脚啦、引脚之间的长度啦、宽度啦&#xff09;&#xff0c;一定要精确。否则等到真正元器件焊在板子上的时候&#xff0c;会发现根本焊不上去&#xff0c;可能就是焊盘的位置不够精确。 可以点击…

初识CSS3

1. 什么是CSS <style>标签 行内样式 内部样式表 外部样式表⭐ CSS样式优先级⭐ 2. CSS3基本选择器 标签选择器 类选择器 ID选择器 基本选择器的特点⭐ 基本选择器的优先级⭐ 3. CSS3高级选择器-层次选择器 后代选择器 子选择器 相邻兄弟选择器 通用兄弟选择器 4. CSS3高级…

Python训练营---Day43

DAY 43 复习日 作业&#xff1a; kaggle找到一个图像数据集&#xff0c;用cnn网络进行训练并且用grad-cam做可视化 进阶&#xff1a;并拆分成多个文件 数据集来源水母图像数据集 --- Jellyfish Image Dataset&#xff0c;对水母图片进行分类&#xff0c;共6个类别。 数据集文件…

NLP学习路线图(十八):Word2Vec (CBOW Skip-gram)

自然语言处理&#xff08;NLP&#xff09;的核心挑战在于让机器“理解”人类语言。传统方法依赖独热编码&#xff08;One-hot Encoding&#xff09; 表示单词&#xff0c;但它存在严重缺陷&#xff1a;每个单词被视为孤立的符号&#xff0c;无法捕捉词义关联&#xff08;如“国…

win32相关(事件)

事件 什么是事件&#xff1f; 事件是指系统或应用程序中发生的特定动作或状态变化&#xff0c;这些动作或变化可以被程序检测并响应。Windows 采用事件驱动的编程模型&#xff0c;应用程序主要通过处理各种事件来与用户交互 我们来看一下事件的函数 HANDLE CreateEventW(LPSE…

VisionPro项目记录3 —— 圆心距

简介&#xff1a;本项目实现基于Cognex视觉系统的两圆心对位功能&#xff0c;使用一个圆作为基准&#xff0c;另一个圆进行补偿&#xff0c;输出偏移值给PLC或机械手。 系统采用CogFindCircleTool定位两圆心坐标&#xff0c;通过脚本计算圆心距并乘以缩放系数kValue&#xff0…

面向连接的运输:TCP

目录 TCP连接 TCP报文段结构 往返时间估计与超时 可靠数据传输 回退N步or超时重传 超时间隔加倍 快速重传 流量控制 TCP连接管理 三次握手 1. 客户端 → 服务器&#xff1a;SYN 包 2. 服务器 → 客户端&#xff1a;SYNACK 包 3. 客户端 → 服务器&#xff1a;AC…

使用Python进行函数作画

前言 因为之前通过deepseek绘制一下卡通的人物根本就不像&#xff0c;又想起来之前又大佬通过函数绘制了一些图像&#xff0c;想着能不能用Python来实现&#xff0c;结果发现可以&#xff0c;不过一些细节还是需要自己调整&#xff0c;deepseek整体的框架是没有问题&#xff0…

C#项目07-二维数组的随机创建

实现需求 创建二维数组&#xff0c;数组的列和宽为随机&#xff0c;数组内的数也是随机 知识点 1、Random类 Public Random rd new Random(); int Num_Int rd.Next(1, 100);2、数组上下限。 //定义数组 int[] G_Array new int[1,2,3,4];//一维数组 int[,] G_Array_T …

java Semaphore‌

Java Semaphore 用于控制同时访问特定资源的线程数量&#xff0c;通过管理一组“许可”&#xff08;permits&#xff09;实现并发限制。 模拟6人上厕所&#xff0c;但只有两个坑位&#xff0c;测试代码&#xff1a; import java.util.concurrent.Semaphore;// 假设厕所只有俩…