首页 > 其他分享 >再来一次基础数论全家桶

再来一次基础数论全家桶

时间:2023-02-17 22:44:42浏览次数:48  
标签:gcd 数论 全家 基础 exgcd times i64 int lcm

约数相关

\(\mathcal{gcd}\)

我100年前的证明自己都已经看不懂了,所以我们这里再浅浅的证明一下。

image

好,于是就可以用递归求 \(\mathcal{gcd}\) 了。

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

\(lcm\)

有一个结论 \(lcm(a, b) \times \gcd(a, b) = a \times b\)。

证明

原式就是要证明 \(lcm(a, b) = a \times b \div \gcd(a, b)\)。

设 \(g = \gcd(a, b),a_0 = a / g, b_0 = b / g\),因为 \(g\) 是 \(a\) 和 \(b\) 的最大公约数,所以 \(a_0\) 和 \(b_0\) 显然是互质的。

则 \(lcm(a_0, b_0) = a_0 \times b_0\)。

所以 \(lcm(a, b) = lcm(a_0 \times g, b_0 \times g) = lcm(a_0, b_0) \times g = a_0 \times b_0 \times g = a \times b_0 = a \times b \div g\)。

证毕。

\(\mathcal{exgcd}\)

balbabalba定理(?):\(\forall a, b\),存在一对 \(x, y \in \mathbb{N}\),满足 \(ax + by = \gcd(a, b)\).

奇怪的证明

分类讨论:

  • 当 \(b = 0\) 时,显然此时 \(x = 1, y = 0\) 满足上面的式子。
  • 当 \(b < 0\) 时,则有 \(\gcd(a, b) = \gcd(b, a \mod b)\),即有 \(ax + by = bx + (a \mod b) \times y=bx+(a-\lfloor a/b\rfloor\times b)y=ay+b\times (x-\lfloor a/b\rfloor\times y)\)
    设 \(x_0 = y, y_0 = x-\lfloor a/b\rfloor\times y\),就是有 \(a\times x_0 + b\times y_0 = \gcd(a, b)\),欧几里得算法的递归过程应用数学归纳法,可以知道这个定理时成立的,同时也可以再求 \(\gcd\) 的时候递归同时求出。
void exgcd(int a, int b, int &x, int &y) {
    if (!b) {
        x = 1, y = 0;
        return;
    }
    exgcd(b, b % a, x, y);
    int z = x;
    x = y;
    y = z - (a / b) * x;
}

关于它的解

当 c 是任意数时

这里的我们要解决 \(ax + by = c\) 的不定方程, \(c\) 可以是任意的一个非 0 数。

这里设 \(g = \gcd(a, b)\)

转化一下就可以得到:\(\frac{g}{c}ax + \frac{g}{c}by = g\)

显然,当 \(g\mid c\) 时,原方程有整数解,用 \(exgcd\)即可求解。

通解

我们用 \(exgcd\) 求出的是这个方程的特解,对于这个不定方程,它是有无数个解的,我们可以这样表示它的通解。

\[x = \frac{c}{g}\times x_0 + k \times \frac{b}{g}\\ y = \frac{c}{g}\times y_0 - k\times\frac{a}{g}\ (k\in \mathbb{Z}) \]

显然是成立的,如果你不能理解,就可以把这个 \(x\) 和 \(y\) 带回原来的方程,可以发现两个含有 \(k\) 的部分抵消了。

一个简答的模板题

luogu P5656 【模板】二元一次不定方程 (exgcd)

求一个不定方程的正整数解的个数, \(x, y\) 的可能的最大和最小的正整数解,或者报告无解。

无解的情况很好判断,不在赘述。

我们求完这个方程的一组特解后, \(x\) 和 \(y\) 都又可能小于 \(0\),所以我们可以加入如下操作是他们一定是正数。

由上面的式子可以知道,它们的变化是相反的,如果我们保证了 \(x\) 大于 \(0\) 保证不了 \(y\) 大于 \(0\),那他就是没有正整数解的。

这里为了保证一定是大于 \(0\) 的,我们要用 \(1-x\) 来做上取整。

if (x <= 0) {
	i64 k = ceil((1.0 - x) / b);
	x += k * b;
	y -= k * a;
	if (y <= 0) {
		y += ceil((1.0 - y) / a) * a;
		printf("%lld %lld\n", x, y);
		continue;
	}
}

\(y\) 也是类似的。

现在我们的 \(x,y\) 都一定是正数了。

然后就比较的简单了,对于正整数解的个数,就是 \(x, y\) 中能操作的最多的次数,及 max(ceil(1. * x / b), ceil(1. * y / a))

对于最小的正整数,我们就秉持能减就减的原则,x - floor((x - 1.) / b) * b 就是 \(x\) 的最小正整数解,同时可以注意到,为了保证一定是一个正数,我这里对 \(x\) 进行了减 1,这样才能保证,不然就要特判他是不是 0,如果是 0 那最小的整数解就应该是 \(b\),\(y\) 也是类似的就不说了。

对于最大的正整数解,对于 \(x\) 来说,如果 \(y\) 的解是最小的, \(x\) 的解就是最大的,既然我们已经知道了 \(y\) 的最小正整数解,那么直接带入原方程就可以算出 \(x\) 的最大解, \(y\) 同理。

#define moretest int ___; for (scanf("%d", &___); ___; ___--)
void exgcd(i64 a, i64 b, i64 &x, i64 &y) {
    if (!b) {
        x = 1, y = 0;
        return;
    }
    exgcd(b, a % b, x, y);
    i64 z = x;
    x = y;
    y = z - (a / b) * x;
}
int main() {
    moretest {
        i64 a, b, c;
        read(a, b, c);
        i64 g = gcd(a, b);
        if (c % g) {
            puts("-1");
            continue;
        }
        i64 x, y;
        a /= g, b /= g, c /= g;
        exgcd(a, b, x, y);
        x *= c, y *= c;
        if (x <= 0) {
            i64 k = ceil((1.0 - x) / b);
            x += k * b;
            y -= k * a;
            if (y <= 0) {
                y += ceil((1.0 - y) / a) * a;
                printf("%lld %lld\n", x, y);
                continue;
            }
        }
        if (y <= 0) {
            i64 k = ceil((1.0 - y) / a);
            x -= k * b;
            y += k * a;
            if (x <= 0) {
                x += ceil((1.0 - x) / b) * b;
                printf("%lld %lld\n", x, y);
                continue;
            }
        }
        // printf("a = %lld b = %lld x = %lld y = %lld\n", a, b, x, y);
        vector<i64> ans;
        ans.pb(max(ceil(1. * x / b), ceil(1. * y / a)));
        // x 可能的最小值
        i64 X = x - floor((x - 1.) / b) * b;
        // y 可能的最小值
        i64 Y = y - floor((y - 1.) / a) * a;
        ans.pb(X);
        ans.pb(Y);
        ans.pb((c - Y * b) / a);
        ans.pb((c - X * a) / b);
        for (auto v : ans) printf("%lld ", v);
        puts("");
    }
    return 0;
}

标签:gcd,数论,全家,基础,exgcd,times,i64,int,lcm
From: https://www.cnblogs.com/Zheng-XiangYu/p/17131575.html

相关文章

  • 基础数论
    基础数论前置芝士质数与约数整除分块欧拉函数模运算与逆元前置芝士:等比数列求和:\(S_n=a_0\frac{1-q^n}{1-q}\)质数与约数:整除与约数质数与合数的定义质数......
  • LaTex第一天-基础学习
    在线LaTeX编辑器:https://www.overleaf.comTeXLive下载:https://www.tug.org/texlive/acquire-iso.htmlMikTeX下载:https://miktex.org/downloadLaTeX公式编辑器:https://......
  • Ajax基础
    什么是Ajax(AsynchronousJavascriptAndXML)? 异步刷新请求(服务),一般是在无需请求整个页面时执行的操作,局部页面发生改变。为什么使用Ajax? 无刷新:不用刷新整个页面,只刷新局......
  • Java面向对象基础
    Java面向对象基础什么是面向对象编程,Java类和对象有什么区别OOP(ObjectOrientedProgramming)编程是利用“类”和“对象”来创建模型实现对真实世界的描述使程序更加......
  • Java基础知识点(数组遍历以及常见问题)
    一:数组遍历:将数组中的所有内容取出来,取出来之后可以对它进行一系列的操作。注意:遍历指的是取出数据的过程,不要局限的理解为遍历就是打印。在Java中,关于数组的一个长度属性.l......
  • Java基础知识点(数组较难的的一个练习-数组的排序)
    冒泡排序:第一步:从第一个元素开始,将相邻的两个元素进行比较,如果前一个元素比后一个元素大,则交换他们的位置,直到最后两个元素完成比较。整个过程完成后,数组中最后一个元素自然......
  • 【LeetCode二叉树#00】二叉树的基础知识
    基础知识分类满二叉树如果二叉树中除了叶子结点,每个结点的度都为2,则此二叉树称为满二叉树。完全二叉树除了底层外,其他部分是满的,且底层从左到右是连续的,称为完全二......
  • 面试最常见算法1—树—基础篇
    前言关于树的算法基本解法就三类:递归,队列,栈刷题网站推荐:​​牛客网​​​​Leetcode​​1.二叉树遍历(前序)publicList<Integer>preorderTraversal(TreeNoderoot){......
  • Linux基础实训(利用线程和互斥锁)
                         实验要求(linux)1定义一个长度为8的数组2输入不同的8个(大写)字母(ASDFGHJK)3对字符串进行排序4用线程和互斥锁输出按顺......
  • windows cmd基础命令
    cmdmd新建目录rd 删除目录(非空目录)rd 删除目录下所有文件cd 改变当前目录cd.. 返回上一级目录cd\ 返回根目录d: 切换盘符到D盘dir 显示当前目录下的文件del1.txt 删除......