加入收藏 | 设为首页 | 会员中心 | 我要投稿 武汉站长网 (https://www.027zz.cn/)- 科技、建站、经验、云计算、5G、大数据,站长网!
当前位置: 首页 > 大数据 > 正文

HDU 5666(二进制模拟乘法)

发布时间:2021-01-17 07:25:59 所属栏目:大数据 来源:网络整理
导读:Segment Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1560????Accepted Submission(s): 577 Problem Description ???? Silen August does not like to talk with others.She like to find

Segment

Time Limit: 2000/1000 MS (Java/Others)????Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1560????Accepted Submission(s): 577

Problem Description ???? Silen August does not like to talk with others.She like to find some interesting problems.

???? Today she finds an interesting problem.She finds a segment? x+y=q .The segment intersect the axis and produce a delta.She links some line between? (0,0) ?and the node on the segment whose coordinate are integers.

???? Please calculate how many nodes are in the delta and not on the segments,output answer mod P. ?
Input ???? First line has a number,T,means testcase number.

???? Then,each line has two integers q,P.

????q ?is a prime number,and? 2≤q≤1018,1≤P≤1018,1≤T≤10. ?
Output ???? Output 1 number to each testcase,answer mod P. ?
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;
}

(编辑:武汉站长网)

【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容!

    热点阅读