pe vol31 151~155
最近好像没什么干劲啊…
Problem 151 : C++,裁纸,数学期望
Problem 152 : C++,1/2用整数的平方的倒数的和来表示的方法数
Problem 153 : C++,整除n的高斯整数之和
Problem 154 : C++,(x+y+z)200000 中有多少个系数是1012的整数倍
Problem 155 : C++,用18个相同容量的电容串联并联等能组成多少种不同的电容值
下面是详细内容:
Read more…
大数取余(二) 剩余定理
上次的文章中主要说的都是各种运算对应的取余的计算方式
但是没有提到关于模数的优化
计算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是质数,可以应用质数所特有的方法
另一个是模数小了,这样如果有循环节的话就更容易发现,这就更爽了
define型计算几何模板
本想在寒假期间写点什么的…无奈域名出了点问题…
导致这一个半月里面网站一直处于无法访问的状态…
想起以前积累的计算几何模板…想差不多可以整理下发出来…
不过充斥着define…以及define的奇怪用法…可以说完全是C语言风格的代码…
总之这是一个基于数组和define而不是类和template的模板…会有人看吗…
如果每段代码都注解出一步步怎么得到的话…工程浩大…
结果心血来潮…给几乎每段代码画了个图片…
蓝色是已知,红色是所求…
画了几个才发现…有些还真难用图片表达啊…
那么就开始吧…
Read more…
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++,最大子三角形和,各行预处理下即可
下面是详细内容:
Read more…
flash Electric box 2
Electric box 2
Electric box的第二作…
目标是通过能量的各种形式的转换将能量传输到目标点…
各种神一般的布局…
能量形式…电,光,风,流水,蒸汽,激光,无线,电池,仓鼠(这个怎么也算…)
电…有电线的地方就能传输…
光…灯泡和太阳能电池板…
风…风扇和发电机…
流水…水壶中流不完的水和发电机…
蒸汽…水壶中沸腾不完的水和…蒸汽机?
激光…激光发射器和镜面反射和激光接收器…
无线形式的电流…一次连上了无论走多远都能继续传输…
电池…充电一次就可以一直放出电…
仓鼠…看到食物或听到音乐就会跑步发电…
还有各种稀奇古怪的东西…像钻头啦…teleporter啦…魔法石啦…
最后一关花了半小时才解出…
Electric box 2 Level 40
Tags: flash
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++,数字反向相加后全由奇数位组成,暴力枚举
下面是详细内容:
Read more…
RSS订阅