Submission #2237848

---

Source Code Expand

#include <cstdio>
#include <vector>
#include <algorithm>

using namespace std;

typedef long long LL;
typedef pair<LL, LL> PI;

namespace io
{
	const int maxb = 1<< 15;
	char b[maxb], *s = b, *t = b;
	bool Getchar(char &ch)
	{
		return ch = s == t && (t = (s = b) + fread(b, 1, maxb, stdin)) == b ? 0 : *s ++;

	}
}

LL Getint()
{
	using namespace io;
	char ch;
	while (Getchar(ch) && (ch < '0' || ch > '9'));
	LL s = ch - '0';
	while (Getchar(ch) && ch >= '0' && ch <= '9')
		s = s * 10 + ch - '0';
	return s;
}

const LL INF = 1e18;
const int maxn = 100;
const int Mod = 1e9 + 7;

void Chkadd(int &x, const int &y) { if ((x += y) >= Mod) x -= Mod; }

int n;
LL fib[maxn];
vector<PI> exc[maxn];

#define fir first
#define sec second

void Prepare()
{
	fib[0] = fib[1] = 1;
	for (n = 1; fib[n] <= INF; ++ n)
		fib[n + 1] = fib[n] + fib[n - 1];
	n -= 2;
	exc[1].push_back(PI(1, 2));
	exc[1].push_back(PI(1, 3));
	for (int i = 2; i <= n; ++ i)
	{
		vector<PI> &lst = exc[i - 1], &cur = exc[i];
		int size = lst.size();
		for (int j = 0; j < size; ++ j)
		{
			LL x = lst[j].fir, y = lst[j].sec;
			for (LL z = x + y; z <= fib[i + 2]; z += y)
				cur.push_back(PI(y, z));
		}
	}
}

void Doit()
{
	LL X = Getint(), Y = Getint();
	if (X > Y) swap(X, Y);
	int k;
	for (k = 1; exc[k][0].fir <= X && exc[k][0].sec <= Y; ++ k);
	-- k;
	if (k <= 1)
	{
		printf("1 ");
		if (X == 1) printf("%lld\n", Y % Mod); else puts("4");
		return;
	}
	printf("%d ", k);
	vector<PI> &cur = exc[k - 1];
	int size = cur.size(), ans = 0;
	for (int i = 0; i < size; ++ i)
	{
		LL x = cur[i].fir, y = cur[i].sec;
		if (X < y || Y < x + y) continue;
		Chkadd(ans, (Y - x) / y % Mod);
		if (X < x + y) continue;
		Chkadd(ans, (X - x) / y % Mod);
	}
	printf("%d\n", ans);
	return;
}

int main()
{
	Prepare();
	int Q = Getint();
	while (Q --) Doit();
	return 0;
}

Submission Info

Judge Result