Submission #1314147

---

Source Code Expand

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<set>
#include<map>
#include<queue>
#include<cassert>
#define PB push_back
#define MP make_pair
#define sz(v) (in((v).size()))
#define forn(i,n) for(in i=0;i<(n);++i)
#define forv(i,v) forn(i,sz(v))
#define fors(i,s) for(auto i=(s).begin();i!=(s).end();++i)
#define all(v) (v).begin(),(v).end()
using namespace std;
typedef long long in;
typedef vector<in> VI;
typedef vector<VI> VVI;
in ma,mb;
in sc;
in sm;
in ts,tx,ty;
const in mdl=1000000007;
VI amax,amay,ambx,amby;
void sup(in x, in y, in s){
  if(amax[s]*x+amay[s]*y>ma)
    return;
  if(ambx[s]*x+amby[s]*y>mb)
    return;
  if(s==sc){
    sm+=(ma-x)/y+1;
    if(x<=mb){
      ++sm;
    }
    sm%=mdl;
    return;
  }
  sup(x+y,y,s);
  sup(x+y,x,s+1);
}
void slv(){
  if(mb>ma)
    swap(mb,ma);
  if(mb==1){
    cout<<1<<" "<<ma%mdl<<"\n";
    return;
  }
  if(mb==2 && ma==2){
    cout<<1<<" "<<4<<"\n";
    return;
  }
  in x=2;
  in y=1;
  sc=2;
  while(x+y<=ma && x<=mb){
    y+=x;
    swap(x,y);
    ++sc;
  }
  amax[sc]=1;
  amay[sc]=0;
  ambx[sc]=0;
  amby[sc]=1;
  for(in i=sc-1;i>=2;--i){
    amax[i]=amax[i+1]+amay[i+1];
    amay[i]=amax[i+1];
    ambx[i]=ambx[i+1]+amby[i+1];
    amby[i]=ambx[i+1];
  }
  cout<<sc-1<<" ";
  sm=0;
  sup(2,1,2);
  cout<<sm<<"\n";
}
int main(){
  ios::sync_with_stdio(0);
  cin.tie(0);
  amax=amay=ambx=amby=VI(200);
  in q;
  cin>>q;
  forn(z,q){
    cin>>ma>>mb;
    slv();
  }
  return 0;
}

Submission Info

Judge Result