类欧几里得算法浅谈(部分)
【类欧几里得算法浅谈(部分)】
学习类欧几里得算法,因为是蒟蒻,感觉网上很多都看不懂,所以自己写一篇快活快活
第一类求和式:
\(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*i+b}{c}\rfloor\) =\(\sum_{i=0}^n(\lfloor\frac{a\mod c*i+b\mod c}{c}\rfloor+\lfloor\frac{a*i}{c}\rfloor+\lfloor\frac{b}{c}\rfloor)\)
进一步化为递归的形式就是:
\(F(a\%c,b\%c,c,n)+\frac{(n+1)n}{2}*\lfloor\frac{a}{c}\rfloor+(n+1)*\lfloor\frac{b}{c}\rfloor\)
2.当\(a
\(=\sum_{i=0}^{n}\sum_{j=0}^{m-1}[\lfloor\frac{a*i+b}{c}\rfloor>=j+1]\)
对于:
\([\lfloor\frac{a*i+b}{c}\rfloor>=j+1]\),
我们知道,大于等于去掉下整除依旧成立,于是
\(=\sum_{i=0}^{n}\sum_{j=0}^{m-1}[(\frac{a*i+b}{c})>=j+1]\)
将分母乘过去,\(b\)移过去:
\(=\sum_{i=0}^{n}\sum_{j=0}^{m-1}[a*i>=j*c+c-b]\)
\(a\)除过去:
\(=\sum_{i=0}^{n}\sum_{j=0}^{m-1}[i>=\frac{(j*c+c-b)}{a}]\)
我们注意到,\(j\)的变化与\(i\)是无关的,于是我们可以将两个\(\sum\)交换
\(=\sum_{j=0}^{m-1}\sum_{i=0}^{n}[i>=\frac{(j*c+c-b)}{a}]\)
\(=\sum_{j=0}^{m-1}\sum_{i=0}^{n}[i>\frac{(j*c+c-b-1)}{a}]\)
(分子减一,去掉等号)
去掉内层\(sigma\):
\(=\sum_{j=0}^{m-1} n-\frac{(j*c+c-b-1)}{a}\)
(这个显然等价)
\(=n*m-\sum_{j=0}^{m-1} \frac{(j*c+c-b-1)}{a}\)
老规矩,转换成递归形式:
\(=n*m-F(c,c-b-1,a,m-1)\)
\(code:\)
inline int add(int a,int b){return a+b>=mod?a+b-mod:a+b;
}
inline int sub(int a,int b){return a-b<0?a-b+mod:a-b;
}
inline int mul(ll a,ll b){return a*b=(mod<<1)?a*b%mod:a*b-mod;
}int likegcd(int a,int b,int c,int n)
{
if (!a) return 0;
if (a>=c||b>=c) {
int tmp=likegcd(a%c,b%c,c,n);
tmp=add(add(tmp,mul(mul(mul(n,n+1),inv[2]),a/c)),mul(n+1,b/c));
return tmp;
}
// ll m=((ll)a*n+((ll)b)/(ll)c);
int f=(((ll)a*n)+b)/c;
// prllf("[%lld]",f%mod);
return sub(mul(n,f),likegcd(c,c-b-1,a,f-1));
}
(完)
(待补)
转载于:https://www.cnblogs.com/KatouKatou/p/9745998.html
推荐阅读
- JAVA(抽象类与接口的区别&重载与重写&内存泄漏)
- 为什么你的路演总会超时()
- 标签、语法规范、内联框架、超链接、CSS的编写位置、CSS语法、开发工具、块和内联、常用选择器、后代元素选择器、伪类、伪元素。
- thinkphp|thinkphp 3.2 如何调用第三方类库
- 使用composer自动加载类文件
- 一个健康的APP和健全的人格大体类似
- 种树郭橐驼传(文言句式+古今异义+词类活用+通假字)
- 归乡-序章(世界伊始,人类无所依靠,我的故事就从这里开始...)
- jQuery插件
- 第十六天(请介绍一件让你非常自豪的事情,(不能是职业类的),什么原因感到自豪。)