【2018/10/19测试T1】加密
程序员文章站
2024-02-25 08:15:16
...
【题目】
【分析】
30 pts:
枚举 ∼ 的所有数,存入哈希表,然后 O 查询单个询问。
100 pts:
正解思路就是如何倒序还原每步操作。
关于 ,相当于是解:,可以用扩展欧几里得算法还原这一步。
关于 ,考虑把运算之前的 分为 份,相当于除了第一份,其他的每一份都异或上了前面的一部分。第一份确定,其余部分也可以确定。
于是,我们可以在 O 的时间内解决。
【代码】
#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;
}
上一篇: asp.net页面生命周期详解