edward-solution-0009

从 Trac 迁移的文章

这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。

原文章内容如下：

g(x)本质是x ^ (x >> 1)。仔细想一下会发现这个东西其实就是个逐差法。令r = x ^ (x >> 1).那么从r的2进制高位看下来，最高位肯定是1，然后接下来的那一位等于前一位异或上当前位原来的值，而前一位我们已经知道了，那么再异或一遍就可以取回原来的当前位。一直这样推下去就可以求得原函数。这个操作和我们学的逐差法是差不多的。就是知道a[1]，再知道每个a[i] - a[i - 1]的值(i = 2 .. n)，可以求回原来的a[i]序列。

然后自然地就想到枚举s1, m1。然后求对应的s2, m2(因为如果枚举两个m，或者两个s，中间都要经过g的运算，有了位运算和这种加减混合是不好求的)。

那么现在相当于知道n组数据a[i],b[i]满足b[i] = a[i] * m2 / m2 + (a[i] + s2) % m2，求m2, s2。其实这个这么复杂的运算也就是a[i] + s2 = b[i]和a[i] + s2 - m2 = b[i]这两种情况。而且后者满足b[i] < a[i]...
所以只要找一个a[i] < b[i]，一个a[i] > b[i]的就可以解出m2, s2了...再test一下是否满足全部即可。

g(x)本质是x ^{(x >> 1)。仔细想一下会发现这个东西其实就是个逐差法。令r = x} (x >> 1).那么从r的2进制高位看下来，最高位肯定是1，然后接下来的那一位等于前一位异或上当前位原来的值，而前一位我们已经知道了，那么再异或一遍就可以取回原来的当前位。一直这样推下去就可以求得原函数。这个操作和我们学的逐差法是差不多的。就是知道a[1]，再知道每个a[i] - a[i - 1]的值(i = 2 .. n)，可以求回原来的a[i]序列。

然后自然地就想到枚举s1, m1。然后求对应的s2, m2(因为如果枚举两个m，或者两个s，中间都要经过g的运算，有了位运算和这种加减混合是不好求的)。

那么现在相当于知道n组数据a[i],b[i]满足b[i] = a[i] * m2 / m2 + (a[i] + s2) % m2，求m2, s2。其实这个这么复杂的运算也就是a[i] + s2 = b[i]和a[i] + s2 - m2 = b[i]这两种情况。而且后者满足b[i] < a[i]...

所以只要找一个a[i] < b[i]，一个a[i] > b[i]的就可以解出m2, s2了...再test一下是否满足全部即可。