Submission #1347147

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <algorithm>
#include <vector>
#include <cstring>
#include <functional>
#include <set>
#include <map>
#include <cmath>
#include <string>
#include <queue>
#define MOD 1000000007
#define INF 1000000000000000000LL
#define MX 200

using namespace std;
typedef long long int ll;
typedef pair <ll,ll> P;

ll A[MX],B[MX];
vector <P> gt[MX];
int sz;

void init()
{
	sz=0;
	A[sz]=1,B[sz]=0;
	sz++;
	A[sz]=2,B[sz]=1;
	sz++;
	while(1)
	{
		A[sz]=A[sz-1]+B[sz-1];
		B[sz]=A[sz-1];
		if(A[sz]>INF) break;
		sz++;
	}
	vector <P> vx;
	for(int i=0;i<sz;i++)
	{
		if(i==0)
		{
			vx.push_back(P(1,0));
			vx.push_back(P(2,0));
		}
		else if(i==1) 
		{
			vx.clear();
			vx.push_back(P(2,1));
			vx.push_back(P(3,1));
		}
		else
		{
			vector <P> nxt;
			for(int j=0;j<vx.size();j++)
			{
				P p=vx[j];
				ll a=p.second,b=p.first;
				for(int t=1;t<=2;t++)
				{
					a+=b;
					if(a>INF) break;
					if(i+1<sz&&a>=A[i+1]&&b>=B[i+1]) break;
					nxt.push_back(P(a,b));
				}
			}
			vx=nxt;
		}
		gt[i]=vx;
	}
}
P solve(ll X,ll Y)
{
	int mx=0;
	while(mx<sz)
	{
		if(A[mx]>X||B[mx]>Y) break;
		mx++;
	}
	if(mx==1)
	{
		return P(1,1);
	}
	ll ret=0;
	for(int i=0;i<gt[mx-2].size();i++)
	{
		P p=gt[mx-2][i];
		ll a=p.first,b=p.second;
		//printf("%lld %lld : %lld %lld\n",X,Y,a,b);
		swap(a,b);
		if(a<=X&&b<=Y)
		{
			ll nm=(X-a)/b;
			ret+=nm;
			ret%=MOD;
		}
	}
	return P(mx-1,ret);
}
int main()
{
	init();
	int Q;
	scanf("%d",&Q);
	while(Q--)
	{
		ll X,Y;
		scanf("%lld %lld",&X,&Y);
		P p=solve(X,Y);
		P q=solve(Y,X);
		if(p.first!=q.first) p=max(p,q);
		else
		{
			p.second+=q.second;
			if(p.second>=MOD) p.second-=MOD;
			//被るのは(x,x)の組、つまり、(1,1),(2,2)だけ
			if(p.first==1)
			{
				p.second--;
				if(X>=2&&Y>=2) p.second--;
				if(p.second<0) p.second+=MOD;
			}
		}
		printf("%lld %lld\n",p.first,p.second);
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:104:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&Q);
                ^
./Main.cpp:108:27: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld %lld",&X,&Y);
                           ^

Judge Result