度娘百科说： 首先， ax+by = gcd(a, b) 这个公式肯定有解 （( ????? )她说根据数论中的相关定理可以证明，反正我信了） 所以 ax+by = gcd(a, b) * k 也肯定有解 （废话，把x和y乘k倍就好了） 所以，这个公式我们写作ax+by = d，(gcd(a, b) | d) gcd(a, b) | d，表示d能整除gcd，这个符号在数学上经常见 那么已知 a，b 求 一组解 x，y 满足 ax+by = gcd(a, b) 这个公式 1 #include<cstdio>2 typedef long long LL;3 void ext...
要求以下函数： \[f(a, b, c, n) = \sum_{i = 0}^n \lfloor \frac{ai + b}{c} \rfloor\] 设\(a = k_1 \times c + a, b = k_2 \times c + b\)，则 \[\lfloor \frac{ai + b}{c} \rfloor = \lfloor \frac{(k_1 \times c + a) \times i + (k_2 \times c + b)}{c} \rfloor = \lfloor \frac{ai + b}{c} \rfloor + k_1 \times i + k_2\]。 所以\[f(a, b, c, n) = f(a \bmod c, b \bmod c, c, n) + \frac{n(n + 1)}{2} \times \lfloor \fra...
前言 初等数论在OI中应用的基础部分，同机房的AuSquare和zhou2003君早就写完了，一直划水偷懒的Hk-pls表示很方，这才开始了这篇博客. $P.S.$可能会分部分发表。 筛法求素数 埃式筛素数 问题：求$[1,n]$中的所有素数 总体思路就是在$[2,n]$中每当我们找到一个新的素数，在把它加入我们的素数队列的同时我们把它的倍数全部打上标记（包括它自己），下一个没有被标记的数就是新的素数。 void find_prime(int n){memset(used,0,sizeof(...
用的最多的， 就是__gcd(a,b) 求最大公约数了 但是欧几里得算法的作用不单单只有这些 例如 对 ax+by=c; 这个不定方程来说 当 c%gcd(a,b)==0 时候方程有解 对于 贝祖等式： ax+by =gcd(a, b) 这个时候就要考虑 欧几里得算法的拓展形式了。 我们在求 ａ,b的最大公约数时候 用的辗转相除法 就和欧几里得算法密不可分 其实gcd(a,b)=====gcd(b,ａ%b); 拿gcd(16,24)来说 最大公约数为8 dcd(16,24)=gcd(24,16)=gc...
学习类欧几里得算法,因为是蒟蒻,感觉网上很多都看不懂,所以自己写一篇快活快活第一类求和式: \(F(a,b,c,n)=\sum_{i=0}^n\lfloor\frac{a*i+b}{c}\rfloor\)对于这样形式的求和,我们有以下的推导: 1.当\(a>=c\)并且\(b>=c\)时,我们有: 对于\(\lfloor\frac{a}{c}\rfloor\), 它实际等价于\(\lfloor\frac{a\mod c}{c}\rfloor+\lfloor\frac{a}{c}\rfloor\), 于是对于原先的式子,我们可以推出: \(F(a,b,c,d,n)=\sum_{i=0}^n\lfloor\frac{a*...
【辗转相除法求GCD】 欧几里得法求GCD效率较辗转相减法求GCD而言效率要高得多。 算法原理：gcd(a,b)=gcd(b,a mod b) 首先我们可以假设a=k?b+ra=k?b+r（其中的r代表着a/b的余数，也就是a%b的结果） 1.首先我们假设d是a和b的最大公约数，则我们可以知道 a可以整除d，表示为a|b，b也可以整除d,表示为b|d，由于r=a?k?br=a?k?b 其中a是d的倍数，而且b也是d的倍数，那我们可以得到其实r也是d的倍数，换句话说r也是可以整除d. 2.接...
【题目】 poj 1061 青蛙的约会 【题意】 两只青蛙在给定长度的数轴上运动，给定初始位置和跳跃每次的长度，问在什么时候两只青蛙能相遇。 【思路】 根据题意有x+mt=y+nt+kl，t表示跳跃次数。变化一下得到式子x-y=(n-m)*t+k*l，形如ax+by=c，因此考虑使用拓展欧几里得算法，求出最小的跳跃次数。 【代码】#include <cstdio> #include <cstdlib> #include <cstring> #include <cmath> #include <cstdlib> #include <map> #include <l...