pe vol31 151~155
最近好像没什么干劲啊…
Project Euler
Problem 151 : C++,裁纸,数学期望
Problem 152 : C++,1/2用整数的平方的倒数的和来表示的方法数
Problem 153 : C++,整除n的高斯整数之和
Problem 154 : C++,(x+y+z)200000 中有多少个系数是1012的整数倍
Problem 155 : C++,用18个相同容量的电容串联并联等能组成多少种不同的电容值
下面是详细内容:
大数取余(二) 剩余定理
上次的文章中主要说的都是各种运算对应的取余的计算方式
但是没有提到关于模数的优化
计算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是质数,可以应用质数所特有的方法
另一个是模数小了,这样如果有循环节的话就更容易发现,这就更爽了
pe vol30 146~150
最近好迷茫…我想做什么?我能做什么?
没有排名…没有考试…没有比较…不知道自己几斤几两…该往什么方向努力…
有能测出人各方面的长处短处的东西会怎么样呢?这样设想着…
Project Euler
pe第三页拖拖拉拉的终于切完了
(最近的新题貌似不太给力啊…老题还是有不少有意思的题目…)
Problem 146 : C++,n^2+k连续素数,减少枚举量
Problem 147 : C++,数矩形,推出式子后就是简单的dp了
Problem 148 : C++,杨辉三角与分形,图形很美,画出图形后算起来就简单多了
Problem 149 : C++,矩阵中行、列、对角线方向的最大子段和
Problem 150 : C++,最大子三角形和,各行预处理下即可
下面是详细内容:
pe vol29 141~145
Project Euler放完假后…发现做了许多不得了的更新…
支持LaTeX这个不错…而且神奇的是…居然是以HTML形式而非图片形式显示的…真的能做到啊…这样也不会有缩放失真…真好…
然后增加了Veterans 这个等级…条件是300+…不过不会显示题数了…也就是说…没法知道是不是解决了100%的题目…
而且这个等级中的排名是按注册时间来的…
这个标准…不会改动吗?否则…比如总题数有600题的时候…貌似扯远了…
不过对防作弊而言是不错的…
最后…那个public profile页面居然不再是public的了…虽然这是引入Veterans等级后的必然结果…因为那里有写用户做了哪些题…
帖子里讨论了很多关于这次改版的事…
为什么题目提供了forum却还是很多人发到公开的博客上呢…
语言障碍和与forum中雷同的思路…很有力的观点…
反驳是…问了很多博客的主人…得到的回答大多数却是:因为别人都这么做…
自问一下…我是什么原因呢…
最初可能是因为…像在oj上做题似的…然后做题会写解题报告…然后…
不过当时貌似是因为WolframAlpha才决定做PE的…?
扯远了…
Project Euler
Problem 141 : C++,找使存在除数,商,余数,形成等比数列的完全平方数,枚举等比数列,判完全平方
Problem 142 : C++,找3个数两两求和求差都是完全平方数,枚举勾股数,注意考虑非本源勾股数
Problem 143 : C++,费马点到三边距离以及三边都是正整数的三角形,枚举内角120度的整数边三角形后配对
Problem 144 : C++,计算几何,椭圆形与直线交
Problem 145 : C++,数字反向相加后全由奇数位组成,暴力枚举
下面是详细内容:
FFT 快速傅立叶变换(任意点)
这个月几乎都在搞保研的事情…结果没拿到资格…算了…也算经历过了…
心血来潮想搞搞FFT玩玩…
虽然在数字信号处理课上有比较详细的讲过…不过是基2的,对于不是2^N点的FFT只能补零吗…
本来是想做做图像的FFT看看…但是图像的边不是2^N点的…而且补零可能也不方便…做滤波估计还会被补的0影响…
不管怎么样…还是先看看基2的FFT怎么做吧…
稍微看了下Wiki上的…貌似还有不少别的方法的FFT…
还是先看看经典的Cooley Tukey算法吧…
离散傅立叶变换的定义式大约是这个样子的
这里用W方便表示,W(a,n)表示极角是a/n个360度的角度,这里关于角度的性质W也有
作为例子,展开个n=8的情况
为了计算右边那一列n个数,直接算要n^2级别的计算量
现在将黄色和绿色的部分分别取出来
X_e和X_o分别是原数列的偶数项和奇数项的离散傅立叶变换,递归的子结构出现了
放到原式中就变成了
这样,只要分别计算出X_e和X_o并附加2*n级别的计算量,就能完成原本要n^2级别的计算量才能完成的运算了
不过毕竟是最基础的方法…代码的运行效率还有很多优化的余地
虽然说是基2的,但是实际上只是个特例
实质上这个方法并不是对分成2份才有效
比如以n=6作为例子,既可以分成2份:
也可以分成3份:
而且依然满足递归的子结构的要求
也就是,n=a*b的情况下,可以分成a份,计算a个长度为b的子序列的离散傅立叶变换值,附加a*n的级别的运算量,就可以完成n点的离散傅立叶变换了
这样,对任意的n都可以做快速傅立叶变换了:分解质因数
可惜n是质数的时候,貌似只能用定义式了…
基2,4,8的情况下,在代码级别上还可以有很好的优化
因为这时会让中间很多步骤中有关W的复数运算简化很多,不用复数乘法,而用实部虚部做较少的加减法来完成
浮点数真是功不可没啊…用很小的精度代价让一个浮点数包含了原序列每个数的一部分信息…就像全息照相一样呢…
pe vol28 136~140
原来project euler也是会放假的…出到299题后停2个月…说会有新的等级出现…
还是慢慢啃老题吧…
Project Euler
Problem 136 : C++,类似Problem 135
Problem 137 : C++,att,考察菲波那契数列为系数的无穷级数收敛到正整数的情况,小数字搜到大数字…
Problem 138 : C++,att,考察边是整数的等腰三角形高与底边大小相差1的情况,还是小数字搜到大数字…
Problem 139 : C++,直角三角形拼正方形,观察一下实际上所需满足的条件,然后枚举本源勾股数处理一下就行了…
Problem 140 : C++,类似Problem 137,使用广义菲波那契数列,小数字找规律得到递推式…
下面是详细内容:
RSS订阅