team2012-E1-mysol-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
数据给出许多 x，求对应 f(x) = g(h2(g(h1(g(x))))) 的函数值

g(x) 实质是序号转格雷码的函数，是一一对应函数，因此它有反函数 h(x)
h(x) 比较复杂，可以用循环一个个处理，也可以像我的程序里那样写

有了 g(x) 和 h(x) 之后，就可以对输入数据和输出数据进行处理
把原函数最内层和最外层的 g(x) 去掉，变成 f'(x) = h2(g(h1(x)))

但是 h2(g(h1(x))) 这玩意还是很难处理，于是暴力破解之
枚举 h1 的两个参数 s1 和 m1，然后进一步处理输入数据，再去掉 g(h1(x))
得到 f''(x) = h2(x) = x / m2 * m2 + (x + s2) % m2

对 h2(x) 进行简单的表达式化简，可以得到
   h2(x) = x / m2 * m2 + (x + s2) % m2
         = x - x % m2 + (x % m2 + s2) % m2
         = x + s2       (当 x % m2 + s2 <  m2 时)
    或者 = x + s2 - m2  (当 x % m2 + s2 >= m2 时)

对于所枚举的 s1 和 m1，检查每一对输入输出数据 u[i] 和 v[i]，
如果 v[i] > u[i]，则 v[i] = u[i] + s2
如果 v[i] < u[i]，则 v[i] = u[i] + s2 - m2
当然，如果 v[i] == u[i] 则枚举的 s1 和 m1 是非法的
根据上面的式子，可以唯一地计算出 s2 和 m2 的值
当然，若 s2 或 m2 不唯一，则说明枚举的 s1 和 m1 也是非法的

在暴力尝试所有 s1 和 m1 的组合之后
只有 s1 = 100007, m1 = 214748 是合法的
对应 s2 = 123123, m2 = 201263

// By 猛犸也钻地 @ 2012.07.19 */
}}}

{{{
#include <cstdio>

unsigned g(unsigned x){return x^x>>1;}
unsigned h(unsigned x){return x^=x>>16,x^=x>>8,x^=x>>4,x^=x>>2,x^x>>1;}

unsigned u[6000],v[6000],x,i,n,s1,m1,s2,m2,w2;

void gao(){
    FILE* dat=fopen("dat","r"),* ans=fopen("ans","r");
    for(n=0;fscanf(dat,"%u",&x)==1;u[n++]=g(x));
    for(n=0;fscanf(ans,"%u",&x)==1;v[n++]=h(x));
    for(m1=1;m1<=345678;m1++)
    for(s1=1+m1*3/10;s1<m1;s1++){
        for(i=s2=w2=0;i<n;i++){
            x=g((u[i]%m1+s1>=m1?s1-m1:s1)+u[i]);
            if(v[i]==x) break;
            if(v[i]> x){
                if(!s2) s2=v[i]-x; else if(s2!=v[i]-x) break;
            }else{
                if(!w2) w2=v[i]-x; else if(w2!=v[i]-x) break;
            }
        }
        if(i==n) printf("%u %u %u %u\n",s1,m1,s2,s2-w2);
    }
}

int main(){
    s1=100007,m1=214748,s2=123123,m2=201263;
    while(scanf("%u",&x)==1){
        x=g(x);
        x=g(x-x%m1+(x%m1+s1)%m1);
        x=g(x-x%m2+(x%m2+s2)%m2);
        printf("%u\n",x);
    }
}
}}}

/* 解题报告 //
给出三个函数，分别是
g(x) = x xor (x / 2)
h1(x) = x / m1 * m1 + (x + s1) % m1
h2(x) = x / m2 * m2 + (x + s2) % m2
数据给出许多 x，求对应 f(x) = g(h2(g(h1(g(x))))) 的函数值
g(x) 实质是序号转格雷码的函数，是一一对应函数，因此它有反函数 h(x)
h(x) 比较复杂，可以用循环一个个处理，也可以像我的程序里那样写
有了 g(x) 和 h(x) 之后，就可以对输入数据和输出数据进行处理
把原函数最内层和最外层的 g(x) 去掉，变成 f'(x) = h2(g(h1(x)))
但是 h2(g(h1(x))) 这玩意还是很难处理，于是暴力破解之
枚举 h1 的两个参数 s1 和 m1，然后进一步处理输入数据，再去掉 g(h1(x))
得到 f''(x) = h2(x) = x / m2 * m2 + (x + s2) % m2
对 h2(x) 进行简单的表达式化简，可以得到
   h2(x) = x / m2 * m2 + (x + s2) % m2
         = x - x % m2 + (x % m2 + s2) % m2
         = x + s2       (当 x % m2 + s2 <  m2 时)
    或者 = x + s2 - m2  (当 x % m2 + s2 >= m2 时)
对于所枚举的 s1 和 m1，检查每一对输入输出数据 u[i] 和 v[i]，
如果 v[i] > u[i]，则 v[i] = u[i] + s2
如果 v[i] < u[i]，则 v[i] = u[i] + s2 - m2
当然，如果 v[i] == u[i] 则枚举的 s1 和 m1 是非法的
根据上面的式子，可以唯一地计算出 s2 和 m2 的值
当然，若 s2 或 m2 不唯一，则说明枚举的 s1 和 m1 也是非法的
在暴力尝试所有 s1 和 m1 的组合之后
只有 s1 = 100007, m1 = 214748 是合法的
对应 s2 = 123123, m2 = 201263
// By 猛犸也钻地 @ 2012.07.19 */

#include <cstdio>
unsigned g(unsigned x){return x^x>>1;}
unsigned h(unsigned x){return x^=x>>16,x^=x>>8,x^=x>>4,x^=x>>2,x^x>>1;}
unsigned u[6000],v[6000],x,i,n,s1,m1,s2,m2,w2;
void gao(){
    FILE* dat=fopen("dat","r"),* ans=fopen("ans","r");
    for(n=0;fscanf(dat,"%u",&x)==1;u[n++]=g(x));
    for(n=0;fscanf(ans,"%u",&x)==1;v[n++]=h(x));
    for(m1=1;m1<=345678;m1++)
    for(s1=1+m1*3/10;s1<m1;s1++){
        for(i=s2=w2=0;i<n;i++){
            x=g((u[i]%m1+s1>=m1?s1-m1:s1)+u[i]);
            if(v[i]==x) break;
            if(v[i]> x){
                if(!s2) s2=v[i]-x; else if(s2!=v[i]-x) break;
            }else{
                if(!w2) w2=v[i]-x; else if(w2!=v[i]-x) break;
            }
        }
        if(i==n) printf("%u %u %u %u\n",s1,m1,s2,s2-w2);
    }
}
int main(){
    s1=100007,m1=214748,s2=123123,m2=201263;
    while(scanf("%u",&x)==1){
        x=g(x);
        x=g(x-x%m1+(x%m1+s1)%m1);
        x=g(x-x%m2+(x%m2+s2)%m2);
        printf("%u\n",x);
    }
}