【HDU ACM Steps刷题记录 Chapter 2】

源代码

https://github.com/stdKonjac/OJ-Submits

刷题记录

2018.9.6

2.1.1 最小公倍数:结论题,最小公倍数(lcm)*最大公约数(gcd)=两数乘积(x*y),反过来lcm=x*y/gcd(x,y)

2.1.2 How many prime numbers:素数判定,对每个数从2到sqrt(x)检查看有没有因子(如果x=2特判即可),有则不是素数,否则是

2.1.3 相遇周期:这哪个神奇出题人出的题,题目解释反了!26501/6335,不是表示转26501圈要6335天,而是26501天能转6335圈……所以行星周期为天数/圈数(得出转一圈需要多少天),然后求两个行星周期的最小公倍数即可。

这里的“分数最小公倍数”,指的是能整除两个分数的最小分数(比如1/6和1/4,最小公倍数就是1/2)。

分数最小公倍数的求法:先把分数化为最简形式,然后最小公倍数即为分子的最小公倍数/分母的最大公约数

还有,本题不用long long的话貌似会WA

2.1.5 又见GCD:说水也水说不水也不水的一道题……最开始直觉以为是c*2就行了,WA了几发,琢磨了一下不对呀,其实很容易举出反例的,比如a=8,c=2,c*2=4 如果b=4,gcd(a,b)=4!=2。但是很显然的b一定是c的倍数,既然b!=c,那么我们就从b=2*c开始一个一个检查直到gcd(a,k*c)=c,答案就是b=k*c

2018.9.7

2.1.4 Cake:挺有意思的一道题。把蛋糕看成一块矩形,首先单