Segment
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 360 Accepted Submission(s): 134
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.
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 1 number to each testcase,answer mod P.
ll ans=0;
ll base=q;
while(num){
if(num%2) ans=(ans+base)%mod;
num/=2;
base=(base+base)%mod;
}
return ans%mod;
}
#include<iostream>
#include<cstring>
#include<cstdio>
#define ll __int64
using namespace std;
int t;
ll q,p;
ll ans1,ans2;
ll re;
ll kuai(ll q,ll num,ll mod){
ll ans=;
ll base=q;
while(num){
if(num%) ans=(ans+base)%mod;
num/=;
base=(base+base)%mod;
}
return ans%mod;
}
int main()
{
while(scanf("%d",&t)!=EOF)
{
for(int i=;i<=t;i++)
{
scanf("%I64d %I64d",&q,&p);
if(q%==)
{
ans1=(q-)/;
ans1=ans1%p;
ans2=q-;
}
else
{
ans1=(q-)/;
ans1=ans1%p;
ans2=q-;
}
printf("%I64d\n",kuai(ans1,ans2,p));
}
}
return ;
}