Submission #1678877

---

Source Code Expand

#include<bits/stdc++.h>
 
#define HEAP priority_queue
#define rep(i, n) for(int i = 0, _end_ = (n); i < _end_; ++i)
#define per(i, n) for(int i = (n) - 1; i >= 0 ; --i)
#define forn(i, l, r) for(int i = (l), _end_ = (r); i <= _end_; ++i)
#define nrof(i, r, l) for(int i = (r), _end_ = (l); i >= _end_; --i)
#define FOR(a, b) for(auto (a): (b))
#define mp make_pair
#define mt make_tuple
#define pb push_back
#define X first
#define Y second
#define eps 1e-6
#define pi 3.1415926535897932384626433832795
#define SZ(x) (int)x.size()
#define ALL(x) x.begin(), x.end()
 
using namespace std;
 
typedef long long LL;
typedef double flt;
typedef vector<int> vi;
typedef vector<LL> vl;
typedef pair<int,int> pii;
typedef pair<int,LL> pil;
typedef pair<LL,int> pli;
typedef pair<LL,LL> pll;
typedef vector<pil> vil;
typedef vector<pii> vii;
typedef vector<pli> vli;
typedef vector<pll> vll;
 
const int iinf = 1e9 + 7;
const int oo = 0x3f3f3f3f;
const LL linf = 1ll << 60;
const flt dinf = 1e60;
 
template <typename T> inline void scf(T &x) {
	bool f = 0;
	x = 0;
	char c = getchar();
	while(c != '-' && (c < '0' || c > '9')) c = getchar();
	if(c == '-') f = 1, c = getchar();
	while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
	if(f) x = -x;
	return;
}
 
template <typename T1, typename T2> void scf(T1 &x, T2 &y) {
	scf(x);
	return scf(y);
}
 
template <typename T1, typename T2, typename T3> void scf(T1 &x, T2 &y, T3 &z) {
	scf(x);
	scf(y);
	return scf(z);
}
 
template <typename T1, typename T2, typename T3, typename T4> void scf(T1 &x, T2 &y, T3 &z, T4 &w) {
	scf(x);
	scf(y);
	scf(z);
	return scf(w);
}
 
inline char mygetchar() {
	char c = getchar();
	while(c == ' ' || c == '\n') c = getchar();
	return c;
}
 
template <typename T> inline bool chkmax(T &x, const T &y) {
	return y > x ? x = y, 1 : 0;
}
 
template <typename T> inline bool chkmin(T &x, const T &y) {
	return y < x ? x = y, 1 : 0;
}
 
#ifdef King_George
#define DEBUG
#define debug(...) fprintf(stderr, __VA_ARGS__)
#else
#define debug(...)
#endif
 
//---------------------------------------------------------head----------------------------------------------------
 
const LL bnd = 1000000000000000000;
 
const int maxn = 100;
 
const LL mod = 1e9 + 7;
 
int n;
LL a[maxn];
vll all[maxn];
LL A, B, res;
 
inline bool inrange(pll x, LL a, LL b) {
	return x.X <= a && x.Y <= b;
}
 
void solve(LL x, LL y) {
	LL t = A / x + 10;
	while(t * x + y > A) {
		--t;
	}
	(res += t) %= mod;
	t = B / x + 10;
	while(t * x + y > B) {
		--t;
	}
	(res += t) %= mod;
	return;
}
 
int main() {
	a[0] = 1;
	a[1] = 2;
	for(n = 2; ; ++n) {
		a[n] = a[n - 1] + a[n - 2];
		if(a[n] > bnd) {
			break;
		}
	}
	all[1].pb(mp(2, 1));
	all[1].pb(mp(3, 1));
	forn(i, 2, n - 1) {
		LL a1 = a[i + 1], b1 = a[i], a2 = a1, b2 = b1;
		--a1;
		--b2;
		for(auto tmp: all[i - 1]) {
			LL a = tmp.X, b = tmp.Y;
			for(LL x = a + b, y = a;;) {
				if(x <= bnd && y <= bnd && (x <= a1 && y <= b1 || x <= a2 && y <= b2)) {
					all[i].pb(mp(x, y));
				}
				else {
					break;
				}
				x += a;
			}
		}
	}
	int Q;
	scf(Q);
	while(Q--) {
		scf(A, B);
		if(A < B) {
			swap(A, B);
		}
		if(B == 1) {
			printf("1 %lld\n", A % mod);
			continue;
		}
		if(A == 2 && B == 2) {
			puts("1 4");
			continue;
		}
		int ans = n - 1;
		while(!inrange(all[ans][0], A, B)) {
			--ans;
		}
		printf("%d ", ans);
		res = 0;
		--ans;
		for(auto tmp: all[ans]) {
			if(tmp.X <= B) {
				solve(tmp.X, tmp.Y);
			}
		}
		printf("%lld\n", res);
	}
	return 0;
}

Submission Info

Judge Result