Submission #1320585

---

Source Code Expand

#include <bits/stdc++.h>

using namespace std;

#define REP(i, a, b) for (int i = (a), i##_end_ = (b); i < i##_end_; ++i)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define mp make_pair
#define x first
#define y second
#define pb push_back
#define SZ(x) (int((x).size()))
#define ALL(x) (x).begin(), (x).end()

#ifdef __WIN32
#define LLFORMAT "I64"
#define Rand() ((rand() << 15) | rand())
#else
#define LLFORMAT "ll"
#define Rand() (rand())
#endif

template<typename T> inline bool chkmin(T &a, const T &b) { return a > b ? a = b, 1 : 0; }
template<typename T> inline bool chkmax(T &a, const T &b) { return a < b ? a = b, 1 : 0; }

typedef long long LL;

const int oo = 0x3f3f3f3f;

const int Mod = 1e9 + 7;

LL n, m;

int Min_step;

pair<pair<LL, LL>, pair<LL, LL> > coe[100];

int ans;

void dfs(LL x, LL y, int res)
{
	if (!res)
	{
		(ans += ((m - y) / x + 1) % Mod) %= Mod;
		if (y <= n && x != y) (++ans) %= Mod;
		return;
	}
	swap(y, x);
	--res;
	while (1)
	{
		y += x;
		if (y > m) break;
		if (y >= 2 * x && y > n) break;
		if (x * coe[res].x.x + y * coe[res].x.y > n) break;
		if (x * coe[res].y.x + y * coe[res].y.y > m) break;
		dfs(x, y, res);
	}
}

int main()
{
#ifdef matthew99
	freopen("input.txt", "r", stdin);
	freopen("output.txt", "w", stdout);
#endif
	coe[0] = mp(mp(1LL, 0LL), mp(0LL, 1LL));
	REP(i, 1, 100)
	{
		coe[i] = coe[i - 1];
		swap(coe[i].x, coe[i].y);
		coe[i].y.x += coe[i].x.x;
		coe[i].y.y += coe[i].x.y;
	}
	int case_cnt;
	scanf("%d", &case_cnt);
	for (int case_id = 1; case_id <= case_cnt; ++case_id)
	{
		scanf("%" LLFORMAT "d%" LLFORMAT "d", &n, &m);
		if (n > m) swap(n, m);
		ans = 0;
		Min_step = 1;
		while (coe[Min_step + 1].x.x + coe[Min_step + 1].x.y <= n && coe[Min_step + 1].y.x + coe[Min_step + 1].y.y <= m) ++Min_step;
		if (Min_step == 1) ans = (LL)(n % Mod) * (m % Mod) % Mod;
		else dfs(1, 1, Min_step);
		(ans += Mod) %= Mod;
		printf("%d %d\n", Min_step, ans);
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:75:24: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d", &case_cnt);
                        ^
./Main.cpp:78:48: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%" LLFORMAT "d%" LLFORMAT "d", &n, &m);
                                                ^

Judge Result