就是找规律,发现每个父亲和孩子的差值都是距儿子最大的fibonacc
也是可证的
f[i]表示当前月的兔子总数
f[i]=f[i-1]+f[i-2](f[i-2]是新生的,f[i-1]是旧有的)
然后又学了一下set的用法
1 #include<iostream>
2 #include<cstdio>
3 #include<string>
4 #include<algorithm>
5 #include<cmath>
6 #include<vector>
7 #include<map>
8 #include<set>
9 #include<cstring>
10 #define MAXN 1000001
11 #define int long long
12 using namespace std;
13 int l[MAXN],r[MAXN];
14 set<int>v;
15 int f[MAXN];int m;
16 void set_work()
17 {
18 f[1]=1;f[2]=2;
19 v.insert(f[1]);v.insert(f[2]);
20 for(int i=3;i<=60;++i)
21 {
22 f[i]=f[i-1]+f[i-2];
23 v.insert(f[i]);
24 }
25 }
26 int find(int x)
27 {
28 set<int>::iterator it;
29 it=v.lower_bound(x);
30 it--;
31 return *it;
32 }
33 int LCA(int x,int y)
34 {
35 if(x==y)return x;
36 if(x>y)swap(x,y);
37 if(x+1==y)return 1ll;
38 set<int>ss;
39 ss.insert(x);
40 while(x!=1)
41 {
42 x-=find(x);
43 ss.insert(x);
44 }
45 while(y!=1)
46 {
47 y-=find(y);
48 if(ss.count(y)!=0)
49 {
50 return y;
51 }
52 }
53 return 1;
54 }
55 signed main()
56 {
57 scanf("%lld",&m);
58 for(int i=1;i<=m;++i)
59 {
60 scanf("%lld%lld",&l[i],&r[i]);
61 }
62 set_work();
63 for(int i=1;i<=m;++i)
64 {
65 printf("%lld\n",LCA(l[i],r[i]));
66 }
67 }