首页 > 其他 > 详细

【BZOJ4917】Hash Killer IV 乱搞

时间:2017-09-24 10:26:58      阅读:314      评论:0      收藏:0      [点我收藏+]

【BZOJ4917】Hash Killer IV

Description

有一天,tangjz造了一个Hash函数:
unsigned int Hash(unsigned int v){
    unsigned int t = v;
    t = t + (t << 10);
    t = t ^ (t >> 6);
    t = t + (t << 3);
    t = t ^ (t >> 11);
    t = t + (t << 16);
    return t;
}
小Q发现这个函数非常不靠谱,对于任意的t,他可以随手构出个数字v使得Hash(v)=t。
小Q现在想考考你,他将给出Q个t,你需要构造出满足条件的v。

Input

第一行包含一个正整数Q(1<=Q<=100000),表示询问的个数。
接下来Q行,每行一个整数t(0<=t<2^32),表示询问的t。
输入数据保证对于每个t至少存在一组解。

Output

对于每组数据输出一行一个整数,即合法的v,若有多组可行解,输出任意一组。

Sample Input

4
614278301
1228622139
1841720774
2457244278

Sample Output

1
2
3
4

题解:发现每个操作都是能反过来的。对于操作1,3,5,可以看成是原数*一个数,因为乘的是奇数而模数是偶数,所以反过来做的话直接乘逆元就行了。对于2,4操作,首先最高的6/11位是不受影响的,然后依次确定后面的位即可。

#include <cstdio>
typedef unsigned int ui;
ui ans,x;
inline ui work(ui x,int y)
{
	for(int i=31-y;i>=0;i--)	x^=((x&(1u<<(i+y)))>>y);
	return x;
}
int main()
{
	int T;	scanf("%d",&T);
	while(T--)	scanf("%u",&ans),ans*=4294901761u,ans=work(ans,11),ans*=954437177u,ans=work(ans,6),ans*=3222273025u,printf("%u\n",ans);
	return 0;
}

【BZOJ4917】Hash Killer IV 乱搞

原文:http://www.cnblogs.com/CQzhangyu/p/7586226.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!