上次的文章中主要说的都是各种运算对应的取余的计算方式
但是没有提到关于模数的优化
计算a%m时,如果m能小一些的话,通常计算起来就会方便很多
比如可以用更小的内存进行预处理,或者找到循环节之类的很好的东西
在做了Project Euler 330后深刻的感受到了这点…
题中要求对77777777取模,可以看到这和平时常用的对某个质数取模不同,这回是个合数
77777777 = 7 * 11 * 73 * 101 * 137
在过去,看到要对合数取模感觉就不太爽,因为有些性质只有质数才能用,比如组合数取模
这题搞了很久没有进展才想起来还有个剩余定理
对于两两互质的一组整数{m1,m2,…,mn}
设m=m1*m2*…*mn, 也就是m是这组数的乘积
设bi=a%mi, 也就是bi是a对mi取余的余数
已知{b1,b2,…,bn}的话,可以求得a%m
具体做法是找到ci=(m/mi)*k使得ci%mi==1
因为两两互质,所以k只要枚举1~mi-1就一定能找到满足条件的ci
最后a%m=sum{ci*bi}%m
因此当m可以分解质因数时可以分成两两互质的一组数,然后通过计算bi来得到a%m
这样做有2个好处
一个是有可能得到mi是质数,可以应用质数所特有的方法
另一个是模数小了,这样如果有循环节的话就更容易发现,这就更爽了
tags: 模板 author: ben1222 comments: 1 Comment
本想在寒假期间写点什么的…无奈域名出了点问题…
导致这一个半月里面网站一直处于无法访问的状态…
想起以前积累的计算几何模板…想差不多可以整理下发出来…
不过充斥着define…以及define的奇怪用法…可以说完全是C语言风格的代码…
总之这是一个基于数组和define而不是类和template的模板…会有人看吗…
如果每段代码都注解出一步步怎么得到的话…工程浩大…
结果心血来潮…给几乎每段代码画了个图片…
蓝色是已知,红色是所求…
画了几个才发现…有些还真难用图片表达啊…
那么就开始吧…
tags: 图片, 心血来潮, 模板 author: ben1222 comments: 6 Comments
有一类题目会因为求出的结果太大而只要求输出对某个数m取余后的结果,而且这个m是比较小的数,比如不超过32位整数…
而这类大数都是可以由较小的数经过某些运算得到的…
于是我整理了一下对付几种运算的方法…包括四则运算,指数,组合数,塔函数的应对方法…
那么就开始吧…慢慢来…
首先是最常识的加减法:
add_mod(a,b,m){
return ((a%m)+(b%m))%m;
}
别小看加法哦…很多用dp解的题目中靠着加法可是能达到很大的数呢…
minus_mod(a,b,m){
return (a-b+m)%m;
}
减法…会遇到吗?
接着是依然很简单的乘法:
multiply_mod(a,b,m){
return ((a%m)*(b%m))%m;
}
这是当m*m不会溢出时可以用的,同时也是通常的情况…
但是如果m*m连long long都会溢出的话…就需要把一个数一位位拆开来做了…
multiply_mod(a,b,m){
if(b==0)return 0;
return (((b&1)?a:0)+(multiply_mod(a,b>>1,m)<<1)%m)%m;
}
然后是除法,但有点限制:
(a/b)%m
特殊条件:m和b互质
前提:a能被b整除
这个有点特殊,意为虽然不知道a是多少,但是已知c,而且c=a%m,用c和b来求(a/b)%m的方法
虽然需要m和b互质,但是不互质的话也是可以做的,因为a也一定是gcd(b,m)的倍数,具体可以看看这里
需要用到扩展欧几里德来求…
至于扩展欧几里德是什么…去Google一下吧…
extend_euclid(a,b,&x0,&y0){
if(b==0){
x0=1;
y0=0;
return [...]
tags: 模板 author: ben1222 comments: 2 Comments
1259 The Picnic
一些点,二维的,要画一个凸多边形,顶点在这些点上,多边形内不能有别的点,求满足这条件的最大凸多边形面积
求最大凸洞
话说凸洞这词是谁发明的?我是从zy那听来的
dp,枚举凸洞最下的点,然后dp[最后点][倒数第二点]=最大值
直接做要O(n^4),可以优化
O(n^3)的做法可以参考这里
这可以做一个模板…不过这种模板估计很少会用到吧…
感觉这篇没什么含金量…
下面是我的代码:(借鉴了上面那个网址里的方法)
tags: PKU, acm, 模板 author: ben1222 comments: No Comments
1986 Distance Queries
描述部分和1984 Navigation Nightmare一样
要求变成了树上两节点间的距离
经典的LCA问题…
又是一个可以用来做模板的题目…lca/rmq的模板
话说这篇是不是有点水…就好象为了贴代码和说一声模板的事而发的…
或许是为了上面那个链接?
下面是我的代码:
tags: PKU, acm, 模板 author: ben1222 comments: 1 Comment
1981 Circle and Points
用单位圆包住最多的点
点数<=300
说到计算几何,模板是最多的了
这是一道可以制作和改进模板的题
模板内容是:求过两点的直径为给定值的圆
我手算了个公式…好累…不过还是没能避免开平方…
这道题O(n^3)能过,枚举2点和扫一遍所有点
不过貌似有更好的方法?没想出来
下面是我的代码:
tags: PKU, acm, 模板 author: ben1222 comments: No Comments