OI技术宅

Tech Otakus save the world!
Welcome,my dear friends!
【I'm kiana/kiana810@126.com】

【WC2012】算不出的算式

【题目描述】

如果你真的很想玩这个游戏,那么就先看看我的题目吧,搞不定这些的话是没办法通关的哟。第一关其实很简单,只有一个关闭的有密码锁的大门。这大门上写着一个奇怪的算式,估计是要你利用它算出密码来开门吧(果然是老掉牙的情节)。


传说中这个式子中的p和q是两个奇质数,等号右边算出来应该就是密码了吧,你是真的算不出来么?

【输入】

只有一行,两个奇质数,分别表示p,q。

【输出】

 一个数,表示算式结果。

【输入样例】

5 7

【输出样例】

6

【数据范围】

p,q在32位整型范围内。

【题解】

设一条直线y=(p/q)x,则等式的两部分分别表示直线下方和左方的整点,由于p,q互质,所以没有整点在直线上。坐标的范围是(0,0)~((p-1)/2,(q-1)/2),所以计算得(p-1)*(q-1)/4即为答案。

注意特判p=q的情况,这时候直线上有整点,所以直接去化简原式,得(p^2-1)/4即为答案。

【代码】

噗,竟然蒙对了答案……

http://paste.ubuntu.com/8498606/

评论

© OI技术宅 | Powered by LOFTER