Untitled

mail@pastecode.io avatar
unknown
plain_text
2 years ago
1.1 kB
1
Indexable
Never
#include<bits/stdc++.h>
using namespace std;

long long po(long long x,long long y,long long z)
{
	if(y==0)
		return 1;
	else 
	{
		long long w=po(x,y/2,z);
		return ((w*w)%z*(y%2?x:1))%z;
	} 
}

long long add(long long a,long long b,long long c,long long n)
{
	if(!a) 
		return (b/c)*(n+1);
	if(a >= c || b >= c)
		return (n*(n+1)/2)*(a/c) + (n+1)*(b/c) + add(a%c,b%c,c,n);
	long long m = (a*n+b)/c;
		return m*n - add(c,c-b-1,a,m-1);
}

int main()
{
	ios::sync_with_stdio(false);
	int t;
	while(cin>>t)
	{
		while(t--)
		{
			long long p,x,y;
			cin>>p>>x>>y;
			if(x%p==0)
			{
				if(y%p==0)
					cout<<0<<'\n';
				else
					cout<<1<<'\n';
			}
			else if(y%p==0)
				cout<<1<<'\n';
			else if(x%p+y%p==p)
				cout<<p<<'\n';
			else
			{
				int z=po(x+y,p-2,p);
				long long x_1=(x*z)%p;
				long long y_1=(y*z)%p;
				int a=1,b=p-1;
				while(b-a)
				{
					int n=(a+b)/2;
					if((x_1+y_1-1)*n*(n+1)/2 - p*add(x_1,0,p,n) - p*add(y_1,0,p,n)==p*n)
						a=n+1;
					else
						b=n;
				}
				cout<<a<<'\n';
			}
		}
	}
	return 0;
}