Problem H: 平方取中法(midsquare method)

"
Time Limit $1$ 秒/Second(s) Memory Limit $512$ 兆字节/Megabyte(s)
提交总数 $793$ 正确数量 $451$
裁判形式 标准裁判/Standard Judge 我的状态 尚未尝试
难度 分类标签 模拟 位运算
平方取中法(midsquare method)是产生[0,1]均匀分布随机数的方法之一,亦称冯·诺伊曼取中法,最早由冯·诺伊曼(John von Neumann,1903-1957)提出的一种产生均匀伪随机数的方法。这里我们将这个算法稍作修改,产生下一个伪随机的正整数n 不妨设置为 n (1)如果 n不足256 则+256 (2)n表示成32位二进制(高位补0,), (3)舍去n的高16位 (4)计算 n*n表示成32位二进制(高位补0,), (5)舍去高8位,低8位,获得一个16位二进制 这个就是下一个随机数m
一个整数 n


输出用这个算法产生的下一个整数 
16
289
样例解释n=16
n=n+256=272
二进制  272(10)=00000000000000000000000100010000(2)
舍去高16位  n=0000000100010000(2)
t=n*n=00000000000000010010000100000000(2)
k=0000000100100001(2)=289(10)