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
所以我们只需要算三角形里面的整数点即可。
代码
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 |
#include<cstdio> #define LL long long using namespace std; inline LL multi(LL a,LL b,LL P){ LL ret=0; while(b){ if (b&1) ret=(ret+a)%P; b/=2; a=(a+a)%P; } return ret; } LL q,P; LL Ans=0; inline void solve(){ scanf("%lld%lld",&q,&P); if ((q-1LL)&1) printf("%lld\n",multi((q-1LL),(q-2LL)/2LL,P)); else printf("%lld\n",multi((q-1LL)/2LL,(q-2LL),P)); } int main(){ int T=0; while(scanf("%d",&T)!=EOF){ for (int i=1;i<=T;i++) solve(); } } |
原文链接：HDU 5666 Segment
WNJXYKの博客 版权所有，转载请注明出处。
还没有任何评论，你来说两句吧!