Submission #2246069
Source Code Expand
#include<cstdio>
#include<algorithm>
using namespace std;
typedef long long LL;
const int p=1000000007;
struct node { LL x,y; } a[102*102];
LL F[102],x,y,X,Y;
int S[102],E[102],i,j,k,n,m,T,g,Z,an;
char c;
inline char getc()
{
#define VV 10000000
static char s[VV],*l=s,*r=s;
if (l==r)
l=s,r=s+fread(s,1,VV,stdin);
return l==r?0:*l++;
}
LL read(){ LL z=0; do c=getc(); while (c<'0'||c>'9'); while (c>='0'&&c<='9') z*=10,z+=c-'0',c=getc(); return z; }
bool cmp(node a,node b){ return a.x<b.x; }
int gcd(LL a,LL b)
{
int z=0;
if (a<b) swap(a,b);
while (b)
a%=b,swap(a,b);
return z;
}
void solve()
{
S[1]=1,E[1]=g=2,a[1]=(node){1,2},a[2]=(node){1,3};
for (i=2;i<=85;++i)
{
S[i]=g+1;
for (j=S[i-1];j<=E[i-1];++j)
{
x=a[j].x,y=a[j].y;
if (x+y<=F[i+2])
a[++g]=(node){y,x+y};
if (x+(y<<1)<=F[i+2])
a[++g]=(node){y,x+(y<<1)};
}
sort(a+S[i],a+g+1,cmp);
k=S[i];
for (j=S[i]+1;j<=g;++j)
if (a[k].x!=a[j].x||a[k].y!=a[j].y)
a[++k]=a[j];
E[i]=k;
}
}
int main()
{
T=read();
for (F[0]=F[1]=1,i=2;i<=90;++i) F[i]=F[i-1]+F[i-2];
solve();
while (T--)
{
an=0,X=read(),Y=read();
if (X>Y) swap(X,Y);
for (Z=2;F[Z]<=X&&F[Z+1]<=Y;++Z);
--Z;
printf("%d ",Z);
if (Z==1)
printf("%d\n",X%p*(Y%p)%p);
else
{
for (i=S[Z-1];i<=E[Z-1];++i)
{
x=a[i].x,y=a[i].y;
if (y<=X)
an=(an+(Y-x)/y)%p;
if (y<=Y)
an=(an+(X-x)/y)%p;
}
printf("%d\n",an);
}
}
return 0;
}
Submission Info
Submission Time
2018-03-23 13:12:21+0900
Task
F - Kenus the Ancient Greek
User
jjb
Language
C++14 (GCC 5.4.1)
Score
1700
Code Size
1534 Byte
Status
AC
Exec Time
523 ms
Memory
12672 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:70:29: warning: format ‘%d’ expects argument of type ‘int’, but argument 2 has type ‘LL {aka long long int}’ [-Wformat=]
printf("%d\n",X%p*(Y%p)%p);
^
Judge Result
Set Name
Sample
All
Score / Max Score
0 / 0
1700 / 1700
Status
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
251 ms
11136 KB
02.txt
AC
251 ms
11264 KB
03.txt
AC
251 ms
11264 KB
04.txt
AC
251 ms
11136 KB
05.txt
AC
251 ms
11264 KB
06.txt
AC
251 ms
11264 KB
07.txt
AC
252 ms
11264 KB
08.txt
AC
251 ms
11264 KB
09.txt
AC
251 ms
11264 KB
10.txt
AC
251 ms
11264 KB
11.txt
AC
523 ms
11648 KB
12.txt
AC
522 ms
11648 KB
13.txt
AC
165 ms
5760 KB
14.txt
AC
164 ms
5760 KB
15.txt
AC
174 ms
12032 KB
16.txt
AC
174 ms
12032 KB
17.txt
AC
79 ms
11776 KB
18.txt
AC
79 ms
11776 KB
19.txt
AC
453 ms
12672 KB
20.txt
AC
453 ms
12672 KB
21.txt
AC
1 ms
256 KB
22.txt
AC
1 ms
256 KB
23.txt
AC
1 ms
256 KB
24.txt
AC
1 ms
256 KB
s1.txt
AC
1 ms
256 KB
s2.txt
AC
1 ms
256 KB