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

（编辑：核心网）

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