這題不太容易看出來是二分搜…倒是更讓人想到利用 xor。這題另一個難點是 IO ，
據說卡 cin/cout，還有這題的題目也不易讀懂啊。
X Y Z
可以展開成一個數列
<X, X+Z, X+2Z, ...> (X + K * Z <= Y)
以 1 10 1 為例，可以展開成 <1, 2, 3, 4, ..., 10>
另一個例子 2 10 1 則展開成 <2, 3, 4, ..., 10>
題目要求的是在這筆測資內，哪一個數（保證只有一個）的出現次數為奇數，輸出此數與其出現次數
Let O[1], O[2], ... 代表各數的出現次數
其中 O[p] is odd, others is even。
我們設
int C[i] = O[1] + O[2] + ... + O[i]
由
偶數 + 偶數 = 偶數
偶數 + 奇數 = 奇數
可知
for all i < p, C[i] is even
for all i >= p, C[i] is odd
也就是說 C[i] 表為
偶偶偶奇奇奇奇
正負相關性出現了，二分搜可以用了…
所以我們得到策略：對 p 二分搜，藉由判斷 C(p) 是否為奇數，即從
0 0 0 1 1 1 1
中找出第一個 1 是在哪
解的範圍 = [1, max_y]，使用 (lb, ub]。
由定義可知，C(i) 代表 1, 2, 3, ..., i 這些數的出現次數總和。
要得到這個總和，我們計算該筆測資展開所有數列後，有幾個 <= i 的數，
因為所有的數列都是等差數列，我們可以利用等差公式來計算，並不用真的把數列展開。
無解的情況（輸出 "no corruption"）發生在對所有的 i，C[i] 都為 even，
這可以預先判斷掉，藉由判斷 C(max_y) 是否是偶數（即所有數的出現次數總和）。
題目還要求輸出 p 的出現次數 O(p)，這可以利用 C(i) 的定義得到，即 C(p) - C(p-1)
#include <iostream>
#include <algorithm>
#include <vector>
#include <sstream>
#include <cstdio>
#include <cstring>
#include <cstdlib>
using namespace std;
typedef long long ll;
struct S {
ll x, y, z;
};
vector<S> data;
int N;
ll C(ll p) {
// 計算展開的數列中大於等於 p 的數有幾個
ll sum = 0;
for (int i = 0; i < N; i++) {
if (p < data[i].x)
continue;
ll end_term = min(p, data[i].y);
sum += (end_term - data[i].x) / data[i].z + 1;
}
return sum;
}
void solve() {
N = data.size();
// 解的範圍 = [1, maxY]
// 偶偶偶奇奇奇奇 = 0 0 0 1 1 1 1
// (lb, ub]
ll max_y = -1;
for (size_t i = 0; i < N; i++)
if (data[i].y > max_y)
max_y = data[i].y;
// when all C[i] is even
if (C(max_y) % 2 == 0) {
puts("no corruption");
return;
}
ll lb = 0;
ll ub = max_y;
while (ub - lb > 1) {
ll mid = (lb + ub) / 2;
if (C(mid) % 2 == 1) ub = mid;
else lb = mid;
}
printf("%lld %lld\n", ub, C(ub) - C(lb));
}
int main() {
char inp[50];
while (fgets(inp, 50, stdin) != NULL) {
size_t len = strlen(inp);
if (len >= 1 && inp[len-1] == '\n') {
inp[len-1] = '\0';
len--;
}
if (len == 0) {
if (data.size() != 0) {
solve();
data.clear();
}
}
else {
S s; sscanf(inp, "%lld %lld %lld", &s.x, &s.y, &s.z);
data.push_back(s);
}
}
if (data.size() != 0)
solve();
return 0;
}