Submission #1678231

---

Source Code Expand

#include<bits/stdc++.h>
#define rep(i,a,b) for(int i=(a);i<=(b);i++)
#define per(i,a,b) for(int i=(a);i>=(b);i--)
#define forE(i,x) for(int i=head[x];i!=-1;i=ne[i])
using namespace std;
typedef long long i64;
typedef unsigned long long u64;
typedef unsigned u32;
typedef pair<int,int> pin;
#define mk(a,b) make_pair(a,b)
#define lowbit(x) ((x)&(-(x)))
#define sqr(a) ((a)*(a))
#define clr(a) (memset((a),0,sizeof(a)))
#define ls ((x)<<1)
#define rs (((x)<<1)|1)
#define mid (((l)+(r))>>1)
#define pb push_back
#define w1 first
#define w2 second
inline void read(int &x){
	x=0;int f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
	x*=f;
}
inline void judge(){
	freopen("in.txt","r",stdin);
	freopen("out.txt","w",stdout);
}
/*******************************head*******************************/
const i64 inf=1000000000000000000ll;
int Q;
i64 f[400];
int n;
vector<pair<i64,i64> > ex[400];
inline int F(i64 a,i64 b){
	// printf("%d %d\n",a,b);
	if(a>b)return F(b,a);
	if(a==0)return 0;
	return F(b%a,a)+1;
}
const int mod=1e9+7;
int main(){
	read(Q);
	f[0]=1;f[1]=1;int n=1;
	while(f[n]+f[n-1]<=inf){
		n++;
		f[n]=f[n-1]+f[n-2];
	}
	ex[0].pb(mk(0ll,1ll));
	ex[0].pb(mk(0ll,2ll));
	rep(i,1,n){
		for(auto x:ex[i-1]){
			i64 a=x.w1,b=x.w2;
			for(;a+b<=f[i+2];a+=b){
				if(F(b,a+b)==i)
					ex[i].pb(mk(b,a+b));
			}
		}
	}
	while(Q--){
		i64 a,b;
		scanf("%lld%lld",&a,&b);
		if(a>b)swap(a,b);
		int ans=1;
		rep(i,1,n-1){
			if(a>=f[i]&&b>=f[i+1])ans=i;else break;
		}
		printf("%d ",ans);
		i64 cnt=0;
		for(auto x:ex[ans-1]){
			if(x.w2<=a&&x.w2+x.w1<=b&&x.w1!=x.w2)cnt=(cnt+(b-x.w1)/x.w2)%mod;
			swap(a,b);
			if(x.w2<=a&&x.w2+x.w1<=b&&x.w1!=x.w2)cnt=(cnt+(b-x.w1)/x.w2)%mod;
			swap(a,b);
		}
		printf("%lld\n",(ans==1)?1ll*a*b%mod:cnt);
	}
	return 0;
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:63:26: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%lld%lld",&a,&b);
                          ^

Judge Result