Submission #1690072

---

Source Code Expand

#include<bits/stdc++.h>
using namespace std;
typedef double db;
typedef long long ll;
typedef pair<ll,ll> pa;
#define w1 first
#define w2 second
#define ls (x<<1)
#define rs (x<<1|1)
#define mp make_pair
#define pb push_back
#define mid ((l+r)>>1)
#define SZ(x) ((x).size())
#define All(x) (x).begin(),(x).end()
#define rep(i,a,b) for(int (i)=(a);(i)<=(b);(i)++)
#define rep2(i,a,b) for(int (i)=(a);(i)<(b);(i)++)
#define per(i,a,b) for(int (i)=(a);(i)>=(b);(i)--)
#define Rep(p,x) for(int (p)=head[(x)];(p);(p)=nxt[(p)])
template<class T>void read(T&num){
	num=0;T f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')num=num*10+ch-'0',ch=getchar();
	num*=f;
}
int power(int x,int k,int p){int res=1;for(;k;k>>=1,x=1ll*x*x%p)if(k&1)res=1ll*res*x%p;return res;}
const int maxn=5e2+5,mod=1e9+7;
int Q,stp;
ll X,Y,ans,f[maxn];
vector<pa>A[maxn];
void calc(vector<pa>A){
	rep2(i,0,SZ(A)){
		ll a=A[i].w1,b=A[i].w2;
		if(a<b)ans=(ans+(b<=X)*((Y-a)/b))%mod;
		else ans=(ans+(a<=Y)*((X-b)/a))%mod;
	}
}
int main(){
	f[0]=f[1]=1;
	rep(i,2,90)f[i]=f[i-1]+f[i-2];
	A[1].pb(mp(1,2));A[1].pb(mp(1,3));
	A[1].pb(mp(2,1));A[1].pb(mp(3,1));
	rep(i,1,86){
		rep2(j,0,SZ(A[i])){
			ll a=A[i][j].w1,b=A[i][j].w2;
			if(a<b){
				A[i+1].pb(mp(b,a+b));
				if(a+2*b<=f[i+3])A[i+1].pb(mp(b,a+2*b));
			}else{
				A[i+1].pb(mp(a+b,a));
				if(b+2*a<=f[i+3])A[i+1].pb(mp(b+2*a,a));
			}
		}
	}
	read(Q);
	while(Q--){
		read(X);read(Y);
		if(X==1&&Y==1){
			puts("1 1");
			continue;
		}
		if(X>Y)swap(X,Y);
		for(stp=2;;stp++)if(f[stp]>Y||f[stp-1]>X)break;
		stp-=2;
		if(stp==1){
			ans=0;
			rep(i,1,X)ans=(ans+Y/i)%mod;
			rep(i,1,X)rep(j,1,min(Y,ll(i-1)))if(i%j==0)ans=(ans+1)%mod;
			printf("%d %lld\n",stp,ans);
		}else{
			ans=0;
			calc(A[stp-1]);
			printf("%d %lld\n",stp,ans);
		}
	}
	return 0;
}

Submission Info

Judge Result