## 【AtCoder】[Grand Contest 015 F] Kenus the Ancient Greek

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int MOD = 1000000007;
const int LOG = 100;

vector<pair<LL, LL> > num[LOG];

char c = getchar(); LL ret = 0, f = 1;
for (; c < '0' || c > '9'; f = c == '-'? -1: 1, c = getchar());
for (; '0' <= c && c <= '9'; ret = ret * 10 + c - '0', c = getchar());
return ret * f;
}

inline void solve(LL A, LL B) {
if (A < num[2][0].first || B < num[2][0].second) {
printf("1 %d\n", A * B % MOD);
return;
}
for (int i = 2; i < LOG; i++) {
if (A < num[i + 1][0].first || B < num[i + 1][0].second) {
int cnt = 0;
for (int j = 0; j < (int)num[i].size(); j++) {
LL a = num[i][j].first, b = num[i][j].second;
cnt = (cnt + (a <= A && b <= B? (B - b) / a + 1: 0)) % MOD;
cnt = (cnt + (b <= A && a <= B? (A - b) / a + 1: 0)) % MOD;
}
printf("%d %d\n", i, cnt);
return;
}
}
}

inline void prework() {
num[0] = vector<pair<LL,LL> >{make_pair(1, 1)};
for (int i = 1; i < LOG; i++) {
for (int j = 0; j < (int)num[i - 1].size(); ++j) {
LL a = num[i - 1][j].first, b = num[i - 1][j].second;
num[i].push_back(make_pair(b, a + b));
}
LL a = num[i - 1][0].first, b = num[i - 1][0].second;
num[i].push_back(make_pair(a + b, 2 * a + b));
}
}

int main() {
prework();
for (int T = read(); T; T--) {
solve(min(A, B), max(A, B));
}
return 0;
}


## 【日常小测】超级绵羊异或

### 解题报告

1. 若$a \ge c$那么显然$f(a,b,c,n) = f(a \% c,b,c,n) + \lfloor\frac{a}{c}\rfloor \cdot s(n)$
2. 若$b \ge c$那么显然$f(a,b,c,n) = f(a,b\%c,c,n) + \lfloor\frac{b}{c}\rfloor \cdot n$

$y<\lfloor\frac{ax+b}{c}\rfloor = c(y+1) \le ax+b = cy+c-b-1<ax=x>\lfloor\frac{cy+c-b-1}{a}\rfloor$

### Code

#include<bits/stdc++.h>
#define LL long long
using namespace std;

char c=getchar(); int ret=0,f=1;
while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();}
while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();}
return ret*f;
}

LL cal(LL a, LL b, LL c, LL n) {
if (a >= c) return (((n-1)*n/2)*(a/c)&1) ^ cal(a%c, b, c, n);
if (b >= c) return (n * (b/c) & 1) ^ cal(a, b%c, c, n);
if (!a) return (b/c) * n & 1;
LL nw = (a * (n - 1) + b) / c;
return ((n-1) * nw & 1) ^ cal(c, c - b - 1, a, nw);
}

int main() {