欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页

【2018/10/19测试T1】加密

程序员文章站 2024-02-25 08:15:16
...

【题目】

内网传送门
外网传送门

【分析】

30 pts:

枚举 1110710^7 的所有数,存入哈希表,然后 O(1)(1) 查询单个询问。

100 pts:

正解思路就是如何倒序还原每步操作。

关于 t=t+(t<<i)t=t+(t<<i),相当于是解:(2i+1)  xt  (mod  232)(2^i+1)\;x\equiv t\;(mod\;2^{32}),可以用扩展欧几里得算法还原这一步。

关于 t=t(t>>i)t=t∧(t>>i),考虑把运算之前的 tt 分为 32i\lceil\frac{32}{i}\rceil 份,相当于除了第一份,其他的每一份都异或上了前面的一部分。第一份确定,其余部分也可以确定。

于是,我们可以在 O(Qlog  n)(Q*log\;n) 的时间内解决。

【代码】

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const long long Mod=1ll<<32ll;
long long Multiply(long long a,long long b)
{
	long long ans=0;
	while(b)
	{
		if(b&1)
		  ans=(ans+a)%Mod;
		a=(a+a)%Mod;
		b>>=1;
	}
	return ans;
}
void exgcd(long long a,long long b,long long &x,long long &y)
{
	if(!b)
	{
		x=1,y=0;
		return;
	}
	exgcd(b,a%b,y,x);
	y-=a/b*x;
}
long long cinv(long long t)
{
	long long x,y;
	exgcd(t,Mod,x,y);
	return x=(x+Mod)%Mod;
}
int main()
{
//	freopen("encrypt.in","r",stdin);
//	freopen("encrypt.out","w",stdout);
	int n,i;
	long long t;
	scanf("%d",&n);
	for(i=1;i<=n;++i)
	{
		scanf("%lld",&t);
		long long x1,x2,x3,x4,x5,x6;
		t=Multiply(t,cinv((1<<16)+1));
		
		x1=t>>22;
		x2=(t>>11)^(x1<<11);
		x3=t^(x1<<22)^(x2<<11);
		x2^=x1,x3^=x2;
		t=(x1<<22)^(x2<<11)^x3;
		
		t=Multiply(t,cinv((1<<3)+1));
		
		x1=t>>30;
		x2=(t>>24)^(x1<<6);
		x3=(t>>18)^(x1<<12)^(x2<<6);
		x4=(t>>12)^(x1<<18)^(x2<<12)^(x3<<6);
		x5=(t>>6)^(x1<<24)^(x2<<18)^(x3<<12)^(x4<<6);
		x6=t^(x1<<30)^(x2<<24)^(x3<<18)^(x4<<12)^(x5<<6);
		x2^=x1,x3^=x2,x4^=x3,x5^=x4,x6^=x5;
		t=(x1<<30)^(x2<<24)^(x3<<18)^(x4<<12)^(x5<<6)^x6;
		
		t=Multiply(t,cinv((1<<10)+1));
		printf("%lld\n",t);
	}
//	fclose(stdin);
//	fclose(stdout);
	return 0;
}