Segment

  
  
   
   1
2 107
  
  

  
  
   
   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;
}

（编辑：湖南网）

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