HDU 5666 Segment

正文索引 [隐藏]

传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5666

题目翻译

问一个以坐标轴和直线(x + y = q)组成的三角形里面的点,有多少个不在原点和这条直线上整点连线上的。q为质数,答案对P求余。

题解

因为q为质数,从原点到(x,y)的整点数量为gcd(x,y)-1,不包含端点。
而且 gcd(x,y) = gcd(x,q-x) = gcd(x,q) =1
所以我们只需要算三角形里面的整数点即可。

代码