HDU 5666(二进制模拟乘法)
SegmentTime Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1560????Accepted Submission(s): 577Problem Description Input Output Sample Input 1 2 107? Sample Output 0? 分析(转自某博客): 根据题意,是让我们求该直线与第一象限构成的三角形区域中,坐标全为整数点的个数且不包括所连直线的整数点个数,坐标轴上的不算。那么我们可以用区域内的整数点减去所有边上的整数点,就是我们的答案。 1.首先我们求出三角形区域内的整数点,不包括斜边上的点的总个数是,1+2+......+q-2=(q-1)*(q-2)/2. 2.然后我们求出(0,0)与斜边上各整数点的连线上整数点的个数。而(0,0)到(x0,y0)所构成的直线上(除去(x0,y0)外),整数点的个数为gcd(x0,y0)-1. 下面证明一下这个结论...(0,0)到(x0,y0)这条直线方程为y=y0/x0 * x。上下同除以gcd(x0,y0)为,y = (y0/gcd)/(x0/gcd)*x..那么肯定(y0/gcd)与(x0/gcd)是互质的,则y想为整数,则x必须为x0/gcd的整数倍,x范围为0-x0,那么这个区间内的x0/gcd倍数个数为x0/(x0/gcd)=gcd,除去端点(x0,y0),所以为gcd(x0,y0)-1。。。。因此可以推广到一般的情况为(x0,y0)到(x1,y1)构成的直线上,整数点的个数为gcd(x1-x0,y1-y0). 所以我们求出gcd(x0,y0)-1即可,又因为x0+y0=q,且gcd(a,b)=gcd(a,a-b)(a>b)。。所以gcd(x0,y0)=gcd(x0,p-x0)=gcd(x0,p); ?p为质数,,那么gcd(x0,p)只可能是p的倍数或者为1,,又因为x,y是小于p的,,,(x+y=p嘛),,所以gcd(x0,p)=gcd(x0,y0)=1.。。。则gcd(x0,y0)-1=0,那么其它直线上是没有整数点的。因此最终的结果就是(q-1)*(q-2)/2.。。 3。注意坑,,q的范围很大,,,(q-1)*(q-2)已经超过long long 了,所以要用到大数知识,,一是用Java的大数类解决,二是用二进制模拟大数乘法得到。。 代码:
#include <cstdio> #include <cstdlib> #include <algorithm> #include <cstring> #include <iostream> using namespace std; typedef long long int ll; ll F(ll a,ll b,ll mod){ //二进制模拟乘法 ll ans = 0; for( ; b>0; b/=2){ if(b%2){ ans += a; ans %= mod; } a = 2*a%mod; } return ans; } int main(){ ll q,P; int T; scanf("%d",&T); ll ans,tmp1,tmp2; while(T--){ cin >> q; cin >> P; tmp1 = (q-1)/2; tmp2 = q-2; ans = F(tmp2,P); cout << ans << endl; } return 0; } (编辑:武汉站长网) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |