字符加密 Valentino 函数 (伪分治)

题面

字符加密 Valentino 函数 (伪分治)

字符加密 Valentino 函数 (伪分治)

$ solution: $

这一题重点不在字符串加密,而是我们最后的求值: $ K^{s}\mod M $ ( $ s\leq36^{100000} $ )

而我们发现它的指数十分巨大,但众所周知的指数不能直接取模,所以我们进行一些优化。

首先,我们 $ O(n) $ 走一遍字符串,求出它加密所需要的进制 $ p $ ,然后我们将 $ K^s $ 进行数位处理,发现我们最终要求的值就是(其中 $ i $ 是我们 $ s $ 的位数):

$ \prod K^{a[i]\times p^{i-1}} $

然后我们发现我们的 $ p^{i-1} $ 部分仍然有可能溢出,但是如果我们将它换成:

$ \prod K^{a[i]\times p\times p\times p......\times p} $

然后不断将上述式子用快速幂求值即可(因为是底数所以取模没问题)(当然我们还可以先预处理一下 $ K^{p\times p\times p........\times p} $ 这个部分)

$ code: $

#include<iostream>
#include<cstdio>
#include<iomanip>
#include<algorithm>
#include<cstring>
#include<cstdlib>
#include<ctime>
#include<cmath>
#include<vector>
#include<queue>
#include<map>
#include<set> #define ll long long
#define db double
#define inf 0x7fffffff
#define rg register int using namespace std; int n,m,t;
ll k,a,ans;
int b[100005];
char c[100005]; inline int qr(){
char ch;
while((ch=getchar())<'0'||ch>'9');
int res=ch^48;
while((ch=getchar())>='0'&&ch<='9')
res=res*10+(ch^48);
return res;
} inline ll fast(ll x,int y){//快速幂
ll res=1;
while(y){
if(y&1)res=res*x%m;
x=x*x%m; y>>=1;
}return res;
} int main(){
//freopen("cipher.in","r",stdin);
//freopen("cipher.out","w",stdout);
k=qr(),m=qr();
while(scanf("%s",c+1)!=EOF){
n=strlen(c+1); t=0;
for(rg i=1;i<=n;++i){
if(c[i]>='0'&&c[i]<='9')b[i]=c[i]-'0';
else b[i]=c[i]-'a'+10;
t=max(t,b[i]+1);
}
a=k; ans=1;
for(rg i=n;i;--i){
ans=ans*fast(a,b[i])%m;
a=fast(a,t);
}printf("%lld\n",ans);
}
return 0;
}
上一篇:Python高阶函数及函数柯里化


下一篇:linux文件统计命令和目录统计命令