bzoj2659 [Beijing wc2012]算不出的算式 类欧几里得

bzoj2659 [Beijing wc2012]算不出的算式 类欧几里得

Description

---

曾经有一个老掉牙的游戏放在我面前，我没有珍惜。直到这个游戏停产才追悔莫及。人世间最痛苦的事情莫过于此，如果上天给我一个再玩一次的机会，我一定要，通关！

如果你真的很想玩这个游戏，那么就先看看我的题目吧，搞不定这些的话是没办法通关的哟。第一关其实很简单，只有一个关闭的有密码锁的大门。这大门上写着一个奇怪的算式，估计是要你利用它算出密码来开门吧（果然是老掉牙的情节）。
传说中这个式子中的p和q是两个奇质数，等号右边算出来应该就是密码了吧，你是真的算不出来么？

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

Solution

---

我们把p看成斜率，柿子等价于直线在第一象限下方的整点数量。直接套类欧的模板即可

题解比较nb，实际上两个式子相当于求一个矩形内的整点数量，这样直接算就是O(1)的了

Code

---

#include <stdio.h>typedef long long LL;LL solve(LL n,LL a,LL b,LL c) { if (!c) return 0; if (a>=c||b>=c) { return solve(n,a%c,b%c,c)+(a/c)*n*(n+1)/2+(b/c)*(n+1); } else { LL m=(n*a+b)/c; return n*m-solve(m-1,c,c-b-1,a); } 
}int main(void) {LL p,q; scanf("%lld%lld",&p,&q);printf("%lld\n", solve((p-1)/2,q,0,p)+solve((q-1)/2,p,0,q));return 0;
}