四月 7th, 2011 () 模板 › ben1222 › 1 Comment
上次的文章中主要说的都是各种运算对应的取余的计算方式
但是没有提到关于模数的优化
计算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是质数,可以应用质数所特有的方法
另一个是模数小了,这样如果有循环节的话就更容易发现,这就更爽了
五月 19th, 2010 () Project Euler › ben1222 › No Comments
Project Euler 第288题
An enormous factorial
p是质数
N(p,q)=sum{T(n)*p^n,n=0..q}
T(n)由题目中的生成公式给出,而且T(n)<p
Nfac(p,q)=N(p,q)!
NF(p,q) 是Nfac(p,q)中p因子的个数
求NF(61,10^7) mod 61^10
下面是我的解题过程:
四月 26th, 2010 () 模板 › ben1222 › 2 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 [...]
四月 21st, 2010 () Project Euler › ben1222 › No Comments
Project Euler 第282题
The Ackermann function
ackermann函数A(m,n)定义如下:
求sum{A(n,n),n=0..6}%14^8
下面是我的解题过程:
十一月 25th, 2009 () Project Euler › ben1222 › 1 Comment
Project Euler
Problem 101 : C++,多项式拟合(伪)
Problem 102 : C++,计算几何,判断点在三角形内
Problem 103 : C++,特殊集合的判定
Problem 104 : C++,菲波那契数列,大数前后9位
Problem 105 : C++,特殊集合的判定
下面是详细内容:
RSS订阅