Submission #1372577
Source Code Expand
#include<cstdio>
#include<algorithm>
using namespace std;
#define reg register
typedef unsigned long long ll;
const int N=1010,p=1e9+7;
int T,ans1,ans2;
int inc(int x,int y){x+=y;return x>=p?x-p:x;}
struct seq{
ll f[N];
int cnt,ans1,ans2;
void init(int start){
for (cnt=start+1;f[cnt-1]+f[cnt-2]<=1e18;cnt++)
f[cnt]=f[cnt-1]+f[cnt-2];
cnt--;
for (int i=cnt+1;i<N;i++) f[i]=2e18+1;
}
inline int rank(reg ll x){
reg int l=1,r=cnt,mid;
while (l<r){
mid=(l+r)>>1;
if (f[mid+1]<=x) l=mid+1;else r=mid;
}
return l;
}
inline void calc(reg ll x,reg ll y){
reg int a=rank(x);
if (y<f[a+1]){
ans1=--a;
ans2=((y-f[a-1])/f[a]+(x-f[a-1])/f[a])%p;
}
else{
ans1=a;
ans2=(y-f[a-1])/f[a]%p;
}
}
}A[N];
ll n,m,fib[N];
int times[N][N],Max[N][N],cnt[N][N];
void init_times(){
for (int i=1;i<N;i++)
for (int j=1;j<N;j++){
int x=i,y=j;
if (x<y) swap(x,y);
times[i][j]=times[y][x%y]+1;
Max[i][j]=max(times[i][j],max(Max[i-1][j],Max[i][j-1]));
if (Max[i][j]==times[i][j]) cnt[i][j]++;
if (Max[i][j]==Max[i-1][j]) cnt[i][j]+=cnt[i-1][j];
if (Max[i][j]==Max[i][j-1]) cnt[i][j]+=cnt[i][j-1];
if (Max[i][j]==Max[i-1][j-1]) cnt[i][j]-=cnt[i-1][j-1];
}
}
ll read(){
ll x=0;char ch=getchar();
while (ch>'9'||ch<'0') ch=getchar();
while (ch>='0'&&ch<='9') x=x*10+ch-'0',ch=getchar();
return x;
}
void print(int x){
if (!x) return void(putchar('0'));
static char str[30];
int l=0;
for (;x;x/=10) str[++l]=x%10;
while (l) putchar(str[l--]+'0');
}
int main()
{
init_times();
fib[0]=fib[1]=1;
for (int i=2;i<=87;i++) fib[i]=fib[i-1]+fib[i-2];
for (int i=1;i<=87;i++){
for (int j=0;j<=i+1;j++) A[i].f[j]=fib[j];
A[i].f[i+1]+=fib[i];
A[i].init(i+1);
}
scanf("%d",&T);
while (T--){
n=read();m=read();
if (n>m) swap(n,m);
/*if (n<N&&m<N){
printf("%d %d\n",Max[n][m],cnt[n][m]);
continue;
}*/
if (n==1){
printf("1 %d\n",int(m%p));
continue;
}
if (n==2&&m==2){
puts("1 4");
continue;
}
A[87].calc(n,m);
ans1=A[87].ans1;
ans2=A[87].ans2;
for (int i=86;i;i--) A[i].calc(n,m);
for (int i=86;i;i--)
if (A[i].ans1==ans1&&ans1>i)
ans2=inc(ans2,A[i].ans2);
print(ans1);
putchar(' ');
print(ans2);
putchar('\n');
}
return 0;
}
Submission Info
Submission Time
2017-06-24 14:46:35+0900
Task
F - Kenus the Ancient Greek
User
FoolMike
Language
C++14 (GCC 5.4.1)
Score
1700
Code Size
2335 Byte
Status
AC
Exec Time
725 ms
Memory
18304 KB
Compile Error
./Main.cpp: In function ‘int main()’:
./Main.cpp:76:16: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
scanf("%d",&T);
^
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
639 ms
17408 KB
02.txt
AC
639 ms
17408 KB
03.txt
AC
639 ms
17408 KB
04.txt
AC
639 ms
17408 KB
05.txt
AC
643 ms
17408 KB
06.txt
AC
640 ms
17408 KB
07.txt
AC
640 ms
17408 KB
08.txt
AC
639 ms
17408 KB
09.txt
AC
639 ms
17408 KB
10.txt
AC
640 ms
17408 KB
11.txt
AC
721 ms
16128 KB
12.txt
AC
715 ms
16128 KB
13.txt
AC
667 ms
16000 KB
14.txt
AC
667 ms
16000 KB
15.txt
AC
669 ms
18304 KB
16.txt
AC
669 ms
18304 KB
17.txt
AC
690 ms
17920 KB
18.txt
AC
688 ms
17920 KB
19.txt
AC
722 ms
17792 KB
20.txt
AC
725 ms
17792 KB
21.txt
AC
11 ms
14464 KB
22.txt
AC
11 ms
14464 KB
23.txt
AC
11 ms
14464 KB
24.txt
AC
11 ms
14464 KB
s1.txt
AC
11 ms
14464 KB
s2.txt
AC
11 ms
14464 KB