Segment

Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/65536 K (Java/Others) Total Submission(s): 1815    Accepted Submission(s): 669 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 x+y=p这条直线与坐标轴围成的三角形中不在边界上的整数点有多少个

从x轴开始，向上或者向下（p的正负），依次是p-2， p-3， p-4 …… 1，一共是（p-1）*（p-2）/2个

#include<cstdio> #include<iostream> #define LL long long using namespace std; LL solve(LL a, LL b, LL c){ LL ans = 0; while(b){//加法快速幂，和乘法基本一样 if(b&1) ans = (ans+a)%c; a = 2*a%c; b >>= 1; } return ans; } int main(){ int t; LL q, p; cin >> t; while(t--){ cin >> q >> p; if((q-1)&1) cout << solve((q-2)/2, q-1, p) << endl;//考虑到除2是否丢精度 else cout << solve((q-1)/2, q-2, p) << endl; } return 0; }