Segment

    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=qx+y=q.The segment intersect the axis
andproduce a delta.She links some line between (0,0)(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 <= 1e18 , 1 <= p <= 1e18 , 1 <= T <= 10 ;

样例

input
1
2 107
output
0

题目大意

给定一条直线 x + y = q , 其和坐标轴构成一个三角形,
然后连接(0 , 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 (在求倍数的个数时(0,0)点自动被剔除出去了) ， 除去端点（x0,y0），所以为gcd(x0,y0)-1

因此可以推广到一般的情况为(x0,y0)到(x1,y1)构成的直线上，整数点的个数为gcd(x1-x0,y1-y0) - 1 (不包括端点).

3.所以我们求出所有的点的 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 ;

4.因为q很大,所以用到64位整数乘法

代码

#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>

using namespace std ;

typedef long long LL ;

LL mul(LL a , LL b , LL p)
{
    LL res = 0 ;
    while(b)
    {
        if(b & 1) res = (res + a) % p ;
        b >>= 1 ;
        a = (a + a) % p ;
    }
    return res ;
}

int main()
{
    int t ;
    cin >> t ; 
    while(t--)
    {
        LL q , p ;
        cin >> q >> p ;
        LL t1 = (q - 1) / 2 ;
        LL t2 = q - 2 ;
        LL sum = mul(t1 , t2 , p) ;
        cout << sum << endl ;
    }


    return 0 ;
}

转载:

https://blog.csdn.net/spring371327/article/details/52723945