Q779’s Blog

裴蜀定理及其证明 一、裴蜀定理 对于 \(x,y\) 的二元一次不定方程 \(ax+by=c\) ，其有解的充要条件为 \(\gcd(a,b)\mid c\) 。 1.充分性证明 充分性 若 \(\gcd(a,b)\mid c\) ，则 \(ax+by=c\) 有解。 证明  设 \(k\) 为 \(a,b\) 线性组合的最小非负解。令 \(q=\left\lfloor\dfrac{a}{k}\right\rfloor\) ，则有 \[ \begin{aligned} r&= a-qk = a-q(ax+by) \\[6pt]&=a(1-qx)+b(-qy) \end{aligned} \] 显然 \(r\) 也为 \(a,b\) 线性组合的解，且 \(0\le r \le k\) 。 由于 \(k\) 为最小非负解，故 \(r = 0\) ，那么 \(k \mid a\) 。同理可得 \(k\mid b\) 。 令 \(d=\gcd(a,b)\) ，则 \(k\mid d\) 且 \(d \ge k\) 。 因为 \(d\mid a,d\mid b\) 且 \...

ubuntu 强制卸载vmware player 不知道什么时候下了vmware-player，然后怎么都删不掉 解决方法 打开终端，输入以下指令 locate vmware-player 然后会出现一大堆vmware player的文件 复制一下，再把每一行都加上 sudo rm或sudo rmdir （注：这里注意一下删除顺序，rmdir似乎不能直接删除非空文件夹） 非常简单，非常暴力，直接删除这些文件 当然如果能正常卸载的话还是这个更好一点 sudo vmware-installer -u vmware-player

浅谈舞蹈链(DLX) 一、舞蹈链 舞蹈链 (Dancing links)，也叫 DLX ，是由 Donald Knuth 提出的数据结构，目的是快速实现他提出的X算法。X算法是一种递归算法，时间复杂度不确定，深度优先，通过回溯寻找精确覆盖问题所有可能的解 （以上摘自维基百科） 舞蹈链的主要思想来源于双向链表 我们设 \(l[x]\) 表示元素 \(x\) 的左指针， \(r[x]\) 表示元素 \(x\) 的右指针 显然，如果想要删除元素 \(x\) ，我们可以做以下操作 r[l[x]]=r[x]; // x左侧的元素的右指针指向x右侧的元素 l[r[x]]=l[x]; // x右侧的元素的左指针指向x左侧的元素 那恢复元素 \(x\) 呢？ 我们可以发现删除 \(x\) 的时候， \(x\) 的左右指针并没有改变，即 \(l[x]\) 和 \(r[x]\) 并没有改变，于是我们可以做以下操作 r[l[x]]=x; // x左侧的元素的右指针重新指向x l[r[x]]=x; // x右侧的元素的左指针重新指向x 这样如果 \(x\) 左右两侧没有改变，我们就可以恢复 \(x\) ...

导数的基本公式推导 主要推导了人教版A版数学选择性必修二上直接给出的基本的导数公式 本文写于作者初三暑假，更新于高一暑假 可能含有很多不足，如果您方便的话可以联系我修改 awa 大概率会在高二暑假再更新一次吧 一、导数的四则运算法则 设 \(f(x),~g(x)\) 均为可导函数 命题：\({[f(x) \pm g(x)]}^{\prime} = f^{\prime}(x) \pm g^{\prime}(x)\) 证明： \[ \begin{aligned} {[f(x) \pm g(x)]}^{\prime}&=\lim\limits_{\Delta x\to 0}{\dfrac{f(x+\Delta x)-f(x) \pm\left[g(x+\Delta x)-g(x)\right]}{\Delta x}} \\\\&=\lim\limits_{\Delta x\to 0}{\dfrac{f(x+\Delta x)-f(x)}{\Delta x}} \pm \lim\limits_{\Delta x\to 0}{\dfrac{g(x+\Delta x)-g(...

蒙提霍尔问题及其推广 前言 蒙提霍尔问题在《人教版A版数学选择性必修三》上作为阅读与思考的材料出现 本文会提供一种简单的解法并推广这个著名的问题 蒙提霍尔问题 一、背景 三门问题（Monty Hall problem）亦称为蒙提霍尔问题、蒙特霍问题或蒙提霍尔悖论，大致出自美国的电视游戏节目Let’s Make a Deal。问题名字来自该节目的主持人蒙提·霍尔（Monty Hall） 二、简介 参赛者会看见三扇关闭了的门，其中一扇的后面有一辆汽车，选中后面有车的那扇门可赢得该汽车，另外两扇门后面则各藏有一只山羊。当参赛者选定了一扇门，但未去开启它的时候，节目主持人开启剩下两扇门的其中一扇，露出其中一只山羊。主持人其后会问参赛者要不要换另一扇仍然关上的门。问题是：换另一扇门是否会增加参赛者赢得汽车的几率 （注：以上摘自百度) 三、分析 题面没什么好说的，我们直接来讨论概率问题 根据直觉，我们可能会有以下两种判断 三扇门中有车的概率都是 \(\dfrac{1}{3}\) ，因此不必换门 既然打开了一扇山羊门，那车在剩下两扇门中的概率都为 \(\dfrac{1}{2}\) ，...

全源最短路 Johnson算法 本文写于较早时期，之前对Dijkstra的理解不是很透彻 已经修改了部分显然错误的内容，有空会再仔细检查的 模板题：P5905 【模板】Johnson 全源最短路 题意简述：给定一个包含 \(n\) 个结点和 \(m\) 条带权边的有向图，求全源最短路，可能有负权重的边、重边、自环，部分数据卡 SPFA 算法（还特地针对了SLF优化） 题意很明确，就是卡SPFA、Dijkstra、Floyd的 这题用SPFA可以被卡成\(O(n^2m)\)，Dijkstra不能处理负权重的边，Floyd\(O(n^3)\)肯定超时 说了这么多，就是为了引出我们要讲的 Johnson 算法 Johnson算法可以判断给定的图中有无负环，在无负环时能给出全源最短路时间复杂度 \(O(n^2\log m)\) （Dijkstra采用优先队列优化，详细的分析可以看这边link） Johnson算法的核心为重新赋予权值，使得边权变成非负的新边权，而在运行过程中以Bellman-Ford和Dijkstra（以下提到的Dijkstra都用优先队列优化）作为自己的子程序 一、算法...

无序数组交换任意两个元素 最少交换次数 题目： 属于是经典题了，做完可以去做一下 UOJ233 【IOI2015】Sorting （确信 给定长度为 \(n\) 的排列，将元素升序排序，每次可以交换任意两个元素，最少要交换几次？ 如果是交换相邻两个元素，那就是逆序对的个数，这个本文不会提及（因为已经说完了 例： input: 6 1 4 2 3 5 6 output: 2 swap 2 4 swap 4 3 题解： 对于每个元素，我们将该元素和它的正确位置建边 最后一定是 \(1\sim n\) 个环（自环也算） 对于有 \(k\) 个元素的环，最少交换次数为 \(k-1\) 假设共有 \(p\) 个环，对于第 \(i\) 个环，有 \(k_i\) 个元素，则它的最少交换次数为 \(k_i - 1\) 因此 \[ \mathtt{ans} = \sum\limits_{i=1}^{p}{(k_i-1)} = \sum\limits_{i=1}^{p}{k_i} - p \] 显然 \[ n = \sum\limits_{i=1}^{p}{k_i} \] 所以答案就是 \...

浅谈补码的原理和正确性 前言 upd 2022.2.14 我就该早点看《计算机组成原理》，补码的定义就是 一个 \(n\) 位二进制数 \(N\) 的二进制补码定义为 \(2^n-N\) 不过本文还是严谨证明了它的正确性，以下为原文 补码是怎么来的？ 负数的补码为什么是按位取反（除了符号位）再加 \(1\) ? 补码的正确性能保证吗？ 补码背后的数学原理是什么？ 本文围绕原理和正确性介绍了补码 一、我们为什么用补码？ 我们以 \(8\) 位二进制数为例 \(8\) 位无符号数，可以表示 \(0\sim255\) 以内的数（即 \(00000000 \sim 11111111\) ），那么如果我们要表示负数呢？ 我们都知道正、负号能够表示正、负数，可是计算机“看不懂“，它只能识别 \(0,1\) 于是，就出现了原码 最高位表示数的正负，\(0\) 表示 正 ，\(1\) 表示负 \(8\) 位有符号数，以原码形式存储则可以表示 \(0 \sim 127\)（即 \(00000000 \sim 01111111\) ） 和 \(-127 \sim 0\) （即 \(111111...

ubuntu ibus输入法 突然无法输入 （延迟过高） 解决方法 前言 ibus拼音输入法最近不知道为何出现了一些异常问题（经常卡死） 被困扰了很久后，终于找到了解决办法 upd.20220423 在中文维基上查到了这样的资料 由于读取sqlite词库时有大量的IO操作，ibus-pinyin在系统高负载时输入时有卡住的现象。 upd.20220423 fcitx差点把你们可爱的q779给整没了，现在他继续用ibus了（重装了一遍） upd.20230608 有位热心网友提供了一些参考： 一、具体表现 写代码时，突然键盘像失灵了一样打不出字，过了好一会才慢慢显示出来 可以说延迟太高了 在此期间终端却可以打开，鼠标也可以正常移动 关闭窗口什么的都没问题，就是打不出字 二、解决方法 如果您的ubuntu中除了ibus拼音输入还有英文输入，那这个方法必定有效 首先切换到en，即英语输入(右上角wifi图标旁边) 然后ctrl+alt+t打开终端 输入 ibus restart 重启ibus拼音输入法 切换回ibus输入法，然后你原先输入的就出现了！ 而且可以正常使用了！ ...

ubuntu VMware报错could not open…解决方法 前言 本人在使用VMware时报了这个错 could not open /dev/vmmon:?????? 经过多方查阅资料，为大家提供一个有效的解决办法 一、具体表现 安装好VMware，虚拟机也创建完了 一运行结果就报错了 一开始以为权限问题，用root打开也一样(显然没用) 二、解决方法 需要关闭安全启动 (\(\mathrm{\color{black}{secure \ boot}}\)) 安全启动设计之初作用是防止恶意软件侵入 事实上它能够做到的仅仅是当电脑引导器被病毒修改之后，它会给出提醒并拒绝启动 因此基本上没什么用 什么？在哪里关闭？？ 当然是BIOS里 进入BIOS (开机后出现电脑品牌的图标时狂按F12) 下面看我拍的照片就懂了吧… 注:我的电脑是DELL的，其他品牌的我不知道 图片可能有点糊，还请谅解 改完记得保存哦！ 然后打开ubuntu，虚拟机就可以正常运行了 总结 本文介绍了因安全启动导致的报错的解决方法

ubuntu 追逐鼠标指针的小猫~Oneko 前言 最近发现了一个有趣的软件 Oneko 可以让一只小猫追着鼠标指针跑 是不是很有趣？ 一、下载Oneko 打开终端 sudo apt install oneko 安装即可 然后它就会在应用程序中了 二、使用Oneko 只要输入这个指令就行 oneko 然后就会有以下效果 Oneko 或者也可以添加到收藏夹后直接单击 不过关闭需要右键，选择Oneko STOP 三、自定义Oneko 官方给的参数如下 Usage: oneko [<options>] Options are: -display <display> : Neko appears on specified display. -fg <color> : Foreground color -bg <color> : Background color -speed <dots> -time <microseconds> -idle <dots> -name <name>...

ubuntu 显示键盘按键 前言 在看一些主播玩游戏时，他们屏幕上会有一个虚拟键盘，可以显示按键 当时觉得很神奇，就想着给ubuntu也弄一个 庆幸的是，ubuntu的确有这种软件 一、KeyMon简介 这个软件叫key-mon，全称Keyboard Status Monitor，即键盘状态监视器 注:截图时我按住了shfit键 不过相对于别的软件，这个就显得有些简单 但不可否认的确有效果 二、安装步骤 打开终端 sudo apt install key-mon 安装即可 适用于ubuntu18.04，目前ubuntu20.04也可以用 三、自定义设置 希望更好的体验？ 右键选择Settings...设置就可以了 总结 本文介绍了KeyMon的安装方法 显示键盘按键就这么简单