2012-A3-0009
从 Trac 迁移的文章
这是从旧校内 Wiki 迁移的文章，可能存在一些样式问题，您可以向 memset0 反馈。
原文章内容如下：
题目定义了：g(x) = x xor (x/2)
h1(x) = x / m1 * m1 + ( x + s1) % m1
h2(x) = x / m2 * m2 + ( x + s2) % m2
f(x) = g( h2( g( h1( g( x ) ) ) ) )
然后输入x和输出f(x)，样例里定义了很多数据，要通过样例确定m1,s1,m2,s2,来确定出f(x)。
g很明显是gray函数，于是可以确定出它的反函数，这样可以只需要确定 h2(g(h1(y))),但是，由于中间套了个g，所以无法直接确定出h1(x),和h2(x)。
于是考虑枚举h1或者h2,以枚举h1为例，这样可以得到g(h1(y)),这样只需要确定h2(z),这样还是比较容易的。
观察h2的形式， 当 x%m2+s2<m2时， h2(x)=x+s2,否则h2(x)=x+s2-m2.
这样就只要x和h2(x)，中找到一对大小互异的即可，就可以确定出s2和m2，再判断是否是解即可。
观察数据有很大的随机性，此外夹杂了一些很小的输入和输出，而0.3m2<s2<m2,故至少有0.3的概率可以找到比h2(x)<x的，
那些很小的数据又保证了可以找到h2(x)>x,如果出现相等或矛盾说明不是解,这样的情况很普遍,
我采用的random_shuffle后顺序查找的方法，比较靠RP.
下面的程序用来确定m1,s1,m2,s2,编译时加了O3优化,其他没有特意去优化,在Intel(R) Core(TM)2 Duo CPU T6570 @2.1GHz 和 800MHz的2G内存，下跑了 10m27s,应该还是可以接受的，
复杂度是 m1*s1*（RP成分），RP成分一般是O(常数)，所以跑到题目给定的最大m1=345678和s1,用时大概在30m以内，
最终的m1,s1在最大值的中间偏大位置，是为了避免反向枚举导致的优势。
{{{
#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef unsigned u32;
inline u32 g(u32 x){
return x^x>>1;
}
inline u32 r(u32 x){
x^=x>>16;
x^=x>>8;
x^=x>>4;
x^=x>>2;
return x^=x>>1;
}
vector<pair<u32,u32> > data;
void getdata(){
FILE *tin=fopen("track.in","r"),
*tou=fopen("track.out","r"),
*smp=fopen("sample","w");
for(u32 a,b;fscanf(tin,"%u",&a)==1&&fscanf(tou,"%u",&b)==1;){
a= g(a);b=r(b);
if(a>4000000000u || b>4000000000u)continue;
data.push_back(make_pair(a,b));
}
sort(data.begin(),data.end());
//for(u32 i=0;i<100;++i)
// fprintf(smp,"%u %u\n",data[i].first,data[i].second);
}
inline void check(u32 m1,u32 s1,u32 m2,u32 s2){
if(m1==0 ||m2==0)return;
for(__typeof(data.end()) it=data.begin();it!=data.end();++it){
u32 t=g(it->first/m1*m1+(it->first+s1)%m1);
if( t/m2*m2+(t+s2)%m2 != it->second)return;
}
printf("m1= %u\ns1= %u\nm2= %u\ns2= %u\n",m1,s1,m2,s2);
exit(0);
}
inline void nx(__typeof(data.end())& ii){
++ii;
if(__builtin_expect((ii==data.end()),0))
ii=data.begin();
}
int main(){
getdata();
random_shuffle(data.begin(),data.end());
for(u32 m1=2;m1<=345678;++m1){
__typeof(data.end()) it=data.begin();
for(u32 s1=m1*3ll/10+1,s2,m2,d;s1<m1;++s1){
u32 t =g(it->first/m1*m1+(it->first+s1)%m1);
if(t==it->second)continue;
if(t<it->second){
s2 = it->second -t;
m2 = ~0;
for(nx(it);(t=g(it->first/m1*m1+(it->first+s1)%m1))<it->second;nx(it))
if(it->second!=t+s2)break;
if(t>it->second){m2=t-it->second+s2;}
if(~m2)check(m1,s1,m2,s2);
}else{
d = t- it->second;
m2 =~0;
for(nx(it);(t=g(it->first/m1*m1+(it->first+s1)%m1))>it->second;nx(it))
if(it->second+d!=t)break;
if(t<it->second){s2=it->second-t;m2=s2+d;}
if(~m2)check(m1,s1,m2,s2);
}
}
if(m1%100 ==0){
printf("m1 %u completed\n",m1);
random_shuffle(data.begin(),data.end());
}
}
return -1;
}
}}}
218老的AMD和新的i3，主频好像更高，应该可以更快。
还有输入保证在[0,2^32^),但中间过程和输出可能会超过2^32^,在计算s1,s2,m1,m2,可以只选那些32位能容纳的数据进行计算，足以排除错误的解，
也可以利用32位平台的特性跑得更快。
这样跑出的结果 m1,m2,s1,m2,代入计算即可。
剩下的工作就很轻松了
{{{
#include<iostream>
#include<cassert>
using namespace std;
typedef unsigned long long num;
const num
M1 = 214748,
M2 = 201263,
A1 = 100007,
A2 = 123123;
num g(num x){
return x^(x>>1);
}
num f1(num x){
return x/M1*M1+(x+A1)%M1;
}
num f2(num x){
return x/M2*M2+(x+A2)%M2;
}
int main(){
num x;
for(;cin >> x;){
assert(x<(1ull<<32));
cout << g(f2(g(f1(g(x))))) << endl;
}
}
}}}题目定义了：g(x) = x xor (x/2)
h1(x) = x / m1 * m1 + ( x + s1) % m1
h2(x) = x / m2 * m2 + ( x + s2) % m2
f(x) = g( h2( g( h1( g( x ) ) ) ) )
然后输入x和输出f(x)，样例里定义了很多数据，要通过样例确定m1,s1,m2,s2,来确定出f(x)。
g很明显是gray函数，于是可以确定出它的反函数，这样可以只需要确定 h2(g(h1(y))),但是，由于中间套了个g，所以无法直接确定出h1(x),和h2(x)。
于是考虑枚举h1或者h2,以枚举h1为例，这样可以得到g(h1(y)),这样只需要确定h2(z),这样还是比较容易的。
观察h2的形式， 当 x%m2+s2 这样就只要x和h2(x)，中找到一对大小互异的即可，就可以确定出s2和m2，再判断是否是解即可。 观察数据有很大的随机性，此外夹杂了一些很小的输入和输出，而0.3m2 那些很小的数据又保证了可以找到h2(x)>x,如果出现相等或矛盾说明不是解,这样的情况很普遍, 我采用的random_shuffle后顺序查找的方法，比较靠RP. 下面的程序用来确定m1,s1,m2,s2,编译时加了O3优化,其他没有特意去优化,在Intel(R) Core(TM)2 Duo CPU T6570 @2.1GHz 和 800MHz的2G内存，下跑了 10m27s,应该还是可以接受的， 复杂度是 m1*s1*（RP成分），RP成分一般是O(常数)，所以跑到题目给定的最大m1=345678和s1,用时大概在30m以内， 最终的m1,s1在最大值的中间偏大位置，是为了避免反向枚举导致的优势。 218老的AMD和新的i3，主频好像更高，应该可以更快。 还有输入保证在[0,232),但中间过程和输出可能会超过232,在计算s1,s2,m1,m2,可以只选那些32位能容纳的数据进行计算，足以排除错误的解， 也可以利用32位平台的特性跑得更快。 这样跑出的结果 m1,m2,s1,m2,代入计算即可。 剩下的工作就很轻松了#include<cstdio>
#include<algorithm>
#include<vector>
#include<cstdlib>
#include<ctime>
using namespace std;
typedef unsigned u32;
inline u32 g(u32 x){
return x^x>>1;
}
inline u32 r(u32 x){
x^=x>>16;
x^=x>>8;
x^=x>>4;
x^=x>>2;
return x^=x>>1;
}
vector<pair<u32,u32> > data;
void getdata(){
FILE *tin=fopen("track.in","r"),
*tou=fopen("track.out","r"),
*smp=fopen("sample","w");
for(u32 a,b;fscanf(tin,"%u",&a)==1&&fscanf(tou,"%u",&b)==1;){
a= g(a);b=r(b);
if(a>4000000000u || b>4000000000u)continue;
data.push_back(make_pair(a,b));
}
sort(data.begin(),data.end());
//for(u32 i=0;i<100;++i)
// fprintf(smp,"%u %u\n",data[i].first,data[i].second);
}
inline void check(u32 m1,u32 s1,u32 m2,u32 s2){
if(m1==0 ||m2==0)return;
for(__typeof(data.end()) it=data.begin();it!=data.end();++it){
u32 t=g(it->first/m1*m1+(it->first+s1)%m1);
if( t/m2*m2+(t+s2)%m2 != it->second)return;
}
printf("m1= %u\ns1= %u\nm2= %u\ns2= %u\n",m1,s1,m2,s2);
exit(0);
}
inline void nx(__typeof(data.end())& ii){
++ii;
if(__builtin_expect((ii==data.end()),0))
ii=data.begin();
}
int main(){
getdata();
random_shuffle(data.begin(),data.end());
for(u32 m1=2;m1<=345678;++m1){
__typeof(data.end()) it=data.begin();
for(u32 s1=m1*3ll/10+1,s2,m2,d;s1<m1;++s1){
u32 t =g(it->first/m1*m1+(it->first+s1)%m1);
if(t==it->second)continue;
if(t<it->second){
s2 = it->second -t;
m2 = ~0;
for(nx(it);(t=g(it->first/m1*m1+(it->first+s1)%m1))<it->second;nx(it))
if(it->second!=t+s2)break;
if(t>it->second){m2=t-it->second+s2;}
if(~m2)check(m1,s1,m2,s2);
}else{
d = t- it->second;
m2 =~0;
for(nx(it);(t=g(it->first/m1*m1+(it->first+s1)%m1))>it->second;nx(it))
if(it->second+d!=t)break;
if(t<it->second){s2=it->second-t;m2=s2+d;}
if(~m2)check(m1,s1,m2,s2);
}
}
if(m1%100 ==0){
printf("m1 %u completed\n",m1);
random_shuffle(data.begin(),data.end());
}
}
return -1;
}
#include<iostream>
#include<cassert>
using namespace std;
typedef unsigned long long num;
const num
M1 = 214748,
M2 = 201263,
A1 = 100007,
A2 = 123123;
num g(num x){
return x^(x>>1);
}
num f1(num x){
return x/M1*M1+(x+A1)%M1;
}
num f2(num x){
return x/M2*M2+(x+A2)%M2;
}
int main(){
num x;
for(;cin >> x;){
assert(x<(1ull<<32));
cout << g(f2(g(f1(g(x))))) << endl;
}
}