pe problem 283
Project Euler 第283题
Integer sided triangles for which the area/perimeter ratio is integral.
三角形面积/周长是正整数的整数边三角形
求这样的三角形的面积/周长不超过1000的周长总和
下面是我的解题过程:
大数取余
有一类题目会因为求出的结果太大而只要求输出对某个数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 [...]
pe problem 282
Project Euler 第282题
The Ackermann function
ackermann函数A(m,n)定义如下:
求sum{A(n,n),n=0..6}%14^8
下面是我的解题过程:
pe problem 280
Project Euler 第280题
Ant and seeds
蚂蚁搬种子
5*5的格子上中间的格子里有一个蚂蚁
每次蚂蚁随机向相邻格子移动,不会移出5*5的格子
最底层的5个格子里分别有一个种子
当蚂蚁没有背种子的时候来到最底层有种子的格子里,就会背上种子
当蚂蚁背着种子的时候来到最顶层的没有种子的格子里,就会放下种子
求使种子全放到顶层所需步数的数学期望
下面是我的解题过程:
pe problem 279
Project Euler 第279题
Triangles with integral sides and an integral angle
求三边长都是整数并且三内角中至少有一个是整数(角度制)的三角形个数
周长限定在不超过10^8
下面是我的解题过程:
pe problem 278
Project Euler 第278题
Linear Combinations of Semiprimes
f(a,b,c)是最大的不能用q1*a+q2*b+q3*c=d(q1,q2,q3是非负整数)表示的d
求所有p<q<r<5000的且p,q,r是素数的f(p*q,p*r,q*r)的和
下面是我的解题过程:
RSS订阅