最大公因数与最小公倍数（GCD 与 LCM）
最大公因数（GCD）和最小公倍数（LCM）是数论中最基础的两个概念，很多算法题都会用到。本文先理清定义，再给出基于辗转相除法的 C++ 实现。 一、基本概念因数能整除某个整数的整数，称为这个整数的因数。例如 6 的因数有 1、2、3、6。 公因数如果一个整数同时是几个整数的因数，就称它为这几个整数的公因数；其中最大的一个就是最大公因数（greatest common divisor，GCD）。 公倍数在两个或两个以上的自然数中，如果它们有相同的倍数，这些倍数就是它们的公倍数；其中最小的一个就是最小公倍数（lowest common multiple，LCM）。 二、热身：几组数 a b 最大公因数 gcd 最小公倍数 lcm 12 18 6 36 15 25 5 75 可以先自己想一想：6 和 36、5 和 75 是怎么来的？ 三、最大公因数 GCD英文三个单词正好对应它的含义： greatest：最大的 common：共同的 divisor：因数 辗转相除法（欧几里得算法）这是求 GCD 最经典的方法：不断用较大数除以较小数，把「除数」和「余数」作...
有关蛇形方阵的几种题目和解题思路
蛇形方阵是模拟类题目的经典入门题，核心在于按照「右 → 下 → 左 → 上」的顺序转圈填数。本文记录两道相关题目： 题目一 P5731：两种经典模拟写法； 题目二 P2239：在模拟之外，更进一步的 O(1) 数学解法。 题目一：洛谷 P5731 蛇形方阵题目链接：P5731 【深基5.习6】蛇形方阵 方法一：4 个 while 循环用四个 while 分别控制「右、下、左、上」四个方向的填充。每个方向一直走，直到越界或格子已有值，然后回退一格、转向 90°。 1234567891011121314151617181920212223242526272829303132333435363738394041424344454647484950515253545556#include<iostream>#include<vector> #include<cstdio>using namespace std;int main(){ int n; cin>>n; vector<vector<int>>...
对异或运算符的学习路程
最近在刷洛谷时遇到了 P1161 开灯 这道题，发现了一种非常巧妙的异或解法。本文从常规的数组模拟讲起，再到异或消去，并整理异或运算符的几条核心性质。 方法一：朴素算法 —— 数组模拟思路用一个巨大的 bool 数组记录每盏灯的状态，每经过一次就将对应位置取反（开灯 ↔ 关灯），最后遍历整个数组，找到唯一仍亮着的灯。 1234567891011121314151617181920212223#include<iostream>#include<vector>using namespace std;int main(){ int n; double a,t; vector<bool> b(2000001,0); cin>>n; for(int i=0;i<n;i++){ cin>>a>>t; for(int j=1;j<=t;j++){ int tmp=a*j; b[tmp]=!b[tmp]; } } for(int i=0;i&l...
Hello
欢迎来到我的博客。 这是用 Hexo + Butterfly 主题重新搭建后的第一篇文章，博客部署在 Vercel 上。图床使用了 imgdd。