Submission #1314647


Source Code Expand

#include <bits/stdc++.h>
using namespace std;
typedef signed long long ll;

#undef _P
#define _P(...) (void)printf(__VA_ARGS__)
#define FOR(x,to) for(x=0;x<(to);x++)
#define FORR(x,arr) for(auto& x:arr)
#define ITR(x,c) for(__typeof(c.begin()) x=c.begin();x!=c.end();x++)
#define ALL(a) (a.begin()),(a.end())
#define ZERO(a) memset(a,0,sizeof(a))
#define MINUS(a) memset(a,0xff,sizeof(a))
//-------------------------------------------------------

int Q;
ll F[91];
ll X,Y;

vector<pair<ll,ll>> cand[91];
ll mo=1000000007;

void solve() {
	int i,j,k,l,r,x,y; string s;
	
	F[0]=F[1]=1;
	for(i=2;i<=89;i++) {
		F[i]=F[i-1]+F[i-2];
		for(j=2;j<=i+1;j++) {
			ll a=1,b=1;
			for(x=2;x<=i;x++) {
				ll c=b+a;
				if(x==j) c+=a;
				b=a;
				a=c;
			}
			cand[i].push_back({a,a+b});
			cand[i].push_back({a+b,a});
		}
	}
	
	
	cin>>Q;
	while(Q--) {
		cin>>X>>Y;
		
		if(X>Y) swap(X,Y);
		if(X==1 || (X==2&&Y==2)) {
			cout<<1<<" "<<(X*Y)%mo<<endl;
			continue;
		}
		
		int k=0;
		while(F[k+1]<=X && F[k+2]<=Y) k++;
		ll ret=0;
		FORR(r,cand[k]) if(X>=r.first && Y>=r.second) {
			(ret += 1+(Y-r.second)/r.first)%=mo;
		}
		cout<<k<<" "<<ret<<endl;
		
	}
}


int main(int argc,char** argv){
	string s;int i;
	if(argc==1) ios::sync_with_stdio(false), cin.tie(0);
	FOR(i,argc-1) s+=argv[i+1],s+='\n';
	FOR(i,s.size()) ungetc(s[s.size()-1-i],stdin);
	solve(); return 0;
}

Submission Info

Submission Time
Task F - Kenus the Ancient Greek
User kmjp
Language C++14 (GCC 5.4.1)
Score 1700
Code Size 1432 Byte
Status AC
Exec Time 911 ms
Memory 4224 KB

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 1700 / 1700
Status
AC × 2
AC × 26
Set Name Test Cases
Sample s1.txt, s2.txt
All 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, s1.txt, s2.txt
Case Name Status Exec Time Memory
01.txt AC 680 ms 3456 KB
02.txt AC 670 ms 3456 KB
03.txt AC 661 ms 3456 KB
04.txt AC 666 ms 3456 KB
05.txt AC 667 ms 3456 KB
06.txt AC 670 ms 3456 KB
07.txt AC 669 ms 3456 KB
08.txt AC 675 ms 3456 KB
09.txt AC 669 ms 3456 KB
10.txt AC 665 ms 3456 KB
11.txt AC 749 ms 2048 KB
12.txt AC 748 ms 2048 KB
13.txt AC 578 ms 2048 KB
14.txt AC 578 ms 2048 KB
15.txt AC 610 ms 4224 KB
16.txt AC 606 ms 4224 KB
17.txt AC 561 ms 3968 KB
18.txt AC 553 ms 3968 KB
19.txt AC 911 ms 3712 KB
20.txt AC 909 ms 3712 KB
21.txt AC 2 ms 512 KB
22.txt AC 2 ms 512 KB
23.txt AC 2 ms 512 KB
24.txt AC 2 ms 512 KB
s1.txt AC 2 ms 512 KB
s2.txt AC 2 ms 512 KB