\(f\)函数 \[ f(n,a,b,c)=\sum_{i=0}^{n}\lfloor\frac{ai+b}{c}\rfloor \] 其中\(a\)、\(b\)和\(c\)均为整数。 如果\(a\ge c\)或\(b\ge c\)则可以先分离一部分。否则将后面展开然后交换和号再化简得到\(f(n,a,b,c)=nm-f(m-1,c,c-b-1,a)\)，其中\(m=\frac{am+b}{c}\)。 \(f_{p,q}\)函数 \[ f_{p,q}(n,a,b,c)=\sum_{i=0}^{n}i^p\lfloor\frac{ai+b}{c}\rfloor^q \] 如果\(a\ge c\)或\(b\ge c\)则可以先分离一部分，用二项式定理，转化...
欧几里得算法的自然语言描述 计算两个非负整数p和q的最大公约数： 若q是0，则最大公约数为p。否则将p除以q得到余数r，p和q的最大公约数即为q和r的最大公约数。 数学归纳法证明 基础步骤： 若q = 0，则 gcd(p, q) = gcd(p, 0) = p。 归纳步骤： 令 p = a * q + r， 其中 p、a、q、r 均为非负整数。 设 d 整除 p 和 q， 则 d 可以整除 p - a * q = r，即 p / d = a*q / d + r / d 。 此时， d 为 p，q 的公约数，且 d 为 q，r 的公...
算法起步，遇到的简单的问题有的都是求一些最大公约数或者最小公倍数。 欧几里得算法就是辗转相除。 求a与b的最大公约数。 a%b=c（取余数，a>=b） 若c=0 gcd(a,b)=b; 若c≠0 gcd(a,b)=gcd(b,c); 直到等于零为止。 int gcd(int a,int b){if(a<b) return gcd(b,a);return b?b:gcd(b,a%b); }
「学习笔记」类欧几里得算法 现有多组询问，要求在 \(O(\log n)\) 求三个有趣式子的和。 设 \[f(a,b,c,n)=\sum_{i=0}^{n}\lfloor \frac {ai+b}{c}\rfloor\] \[g(a,b,c,n)=\sum_{i=0}^{n}\lfloor \frac {ai+b}{c}\rfloor^2\] \[h(a,b,c,n)=\sum_{i=0}^{n}i\lfloor \frac {ai+b}{c}\rfloor\] \(t_1=\lfloor \frac ac\rfloor,t_2=\lfloor \frac bc\rfloor\) \(S_1(n)=\sum_{i=0}^{n}i,S_2(n)=\sum_{i=0}^{n}i^2\) \(m=\lfloor \frac {...
哎呀大水题。。我写了一个多小时。。好没救啊。。 数论板子X合一？ 注意: 本文中变量名称区分大小写。 题意: 给一个\(n\)阶递推序列\(f_k=\prod^{n}_{i=1} f_{k-i}b_i\mod P\)其中\(P=998244353\), 输入\(b_1,b_2,...,b_n\)以及已知\(f_1,f_2,...,f_{n-1}=1\), 再给定一个数\(m\)和第\(m\)项的值\(f_m\), 求出一个合法的\(f_n\)值使得按照这个值递推出来的序列满足第\(m\)项的值为给定的\(f_m\). 题解: 首先一个显然的结论是\(f_m\...
青蛙的约会|数论|同余|扩展欧几里得算法为什么这种乐(S)观(B)的青蛙都能网恋，还成功了（我：？？？？？？？SB青蛙去死8 ） 为什么最近一直在做青蛙的题？（我怕是要无限-1s制了？？？？）Problem分析 （先搞懂扩展欧几里得算法8） 根据题意可得： 青蛙A： 初始位置x,每次跳m 青蛙B： 初始位置y,每次跳n 总长度为L 求相遇时间（如果有解）t 即换成数学表达式： \[ x+m\cdot t \equiv y+n\cdot t \left(mod \ L\right) \] 根据分析扩...
目录同余 基本定理 欧拉定理 费马小定理 扩展欧拉定理扩展欧几里得算法同余 基本定理 欧拉定理 若a,m互质，则 \[ a^{\varphi\left ( m \right )}\equiv 1\left ( mod \ m \right ) \] 应用 令，，这两个数是互素的。比5小的正整数中与5互素的数有1、2、3和4，所以。计算：，而。与定理结果相符。 计算的个位数，实际是求被10除的余数。7和10互素，且。由欧拉定理知。所以。费马小定理 若p是质数，则对于任意整数a，都有 \[ a^{p}\e...
内容：已知a, b，求解一组x，y，使它们满足贝祖等式： ax+by =gcd(a, b) 扩展欧几里得算法，就和它的名字一样是对欧几里得算法的扩展。何为扩展？一是，该算法保留了欧几里得算法的本质，可以求a与b的最大公约数。二是，已知a, b求解二元一次方程ax+by =gcd(a, b)的一组解（x，y）。 证明： 假设 a>b, (1) b=0 gcd(a,b) = a , ax = a , 则x=1，y=0;（这里我还是推荐不把gcd(a,0)理解成最大公约数，而是一个计算机求出来的...
http://acm.hdu.edu.cn/showproblem.php?pid=1576先简介下扩展欧几里得算法： 据说可以证明方程ax+by=gcd(a，b)必然有解，而且不止一组解（gcd指最大公约数） 朴素的欧几里得算法就是辗转相除法，用来求gcd的 因为gcd(a，b)=gcd(b，a mod b)=gcd(a mod b，b mod (a mod b))=… 最后会有一方等于0，就能求出gcd(a，b)，这就是辗转相除法 扩展欧几里得算法可以解出方程ax+by=gcd(a，b)的一组解，假设a>b>=0 以下是一段简单的推导： a...
写在前面这篇博客是我在【数论】对 算术基本定理 的研究 中的一部分欧几里得算法欧几里得算法即辗转相除法原理和更项减损术一样的 结合算术基本定理，有GCD(a，b) == P1min(a1,b1)P2min(a2,b2)......Pnmin(an,bn)a MOD b == P1a1-b1P2a2-b2......Pnan-bn(执行的条件为ai>=bi)则能得到GCD(a，b) == GCD(b，a MOD b) 写成GCD(b，a MOD b)而不是GCD(a MOD b，b)，就保证了前一个数必然大于后一个数这样就可以写一个递归函数，一层一层...
Description求关于\(x\)的同余方程 \(ax \equiv 1 \pmod {b}\) 的最小正整数解。 Input一行，包含两个正整数 \(a,b\)用一个空格隔开。 Output一个正整数 \(x_0\)即最小正整数解。输入数据保证一定有解。 Solution #include<cstdio> #include<algorithm> #include<cstring> using namespace std; long long a,b,x,y; void exgcd(long long a,long long b,long long &x,long long &y) {if (b==0){x=1;y=0;return;}exgcd(b,a%b,x,y);l...
eg：求5关于模14的乘法逆元15 = 5*2+1 5 = 4*1+1 说明5与14互素，存在5关于14的乘法逆元 1 = 5-4 = 5-（14-5*2）= 5*3-14 因此5关于模14的乘法逆元为3 a存在模b的乘法逆元的充要条件是gcd（a,b）= 1 互质：两个数的最大公约数为1，则称这两个数互质，也叫互素 对于扩展欧几里得算法求乘法逆元的步骤解析。设a>b 显然当b=0,gcd(a,b)=a. 此时x=1，y=0 当b!=0时 设a*x1+b*y1 = gcd(a,b) b*x2+(a mod b)*y2 = gcd(b,a mod b)因为 gcd(...
#include<iostream> #include<string.h> #include<algorithm> #include<stdio.h> #define ll long long #define rep(i,j,k) for(int i=j;i<=k;++i) using namespace std; const int maxx = 1e4+7; ll a[maxx]; void ex_gcd(ll a,ll b,ll &d,ll &x,ll &y) {if (!b){d=a;x=1;y=0;}else{ex_gcd(b,a%b,d,y,x);y-=x*(a/b);} } int main() {int n;while(~scanf("%d",&n)){memset(a,0,sizeof(a));for (int i=1; i<=2*n; i+=2){scanf("%lld...
本篇将附上扩展欧几里得算法的思想与推导;对于一个方程\(a*x+b*y=gcd(a,b)\)来说,我们可以做如下的推导: 设有\(a*x_1+b*y_1=gcd(a,b)\); 同时我们有\(b*x_2+(a\%b)*y_2=gcd(b,a\%b)\); 对于这个方程组,我们希望知道的是\(x_1,x_2,y_1,y_2\)之间的关系,这样我们才可以递归解决这个问题; 我们观察\(b*x_2+(a%b)*y_2\)这个式子,我们可以将\((a\%b)\)写作\((a-\lfloor\frac{a}{b}\rfloor*b)\),将括号打开常数\(a,b\)合并,合并之后的结果...
我们接着上面的欧几里得算法说 扩展欧几里得算法 扩展欧几里德算法是用来在已知a, b求解一组x，y，使它们满足贝祖等式\(^①\)： ax+by = gcd(a, b) =d（解一定存在，根据数论中的相关定理）。扩展欧几里德常用在求解模线性方程及方程组中。 ①：裴蜀定理: 裴蜀定理\((Bezouts identity)\)是代数几何中一个定理，其内容是若设a,b是整数，则存在整数x,y，使得ax+by=gcd（a,b），(a,b)代表最大公因数，则设a,b是不全为零的整数，则存在...