首页 > 其他 > 详细

UVA12253 【简单加密法 Simple Encryption】

时间:2019-01-18 22:11:03      阅读:117      评论:0      收藏:0      [点我收藏+]

这题到现在还是只有我一个人过?太冷门了吧,毕竟你谷上很少有人会去做往年ACM比赛的题

题面意思很简单,每次给出\(K_1\),让你求一个\(K_2\)满足\(K_1^{K_2}\equiv K_2(\mod 10^{12})\)

题目乍一看很有数学风格,看到取模和幂次想到什么?

费马大小定理,BSGS,二次探测,不过在这里好像都用不了啊。

所以我们先考虑一个最朴素的想法:爆搜,每次直接枚举每一位上放什么数字,然后快速幂判断。

这样肯定T飞啊,所以我们进行一个大力观察,我们手玩下第二个样例:

\[99^9\equiv 9(\mod 10^{1});99^9\equiv 99(\mod 10^{2})\]

\[99^{99}\equiv 99(\mod 10^{2});99^{99}\equiv 899(\mod 10^{3})\]

\[99^{899}\equiv 899(\mod 10^{3});99^{899}\equiv 9899(\mod 10^{4})\]

\(\dots\)

发现什么没,若\(K_1^{n}\equiv dn(\mod 10^{\operatorname{bit}_n+1})\),那么\(K_1^{dn}\equiv dn(\mod 10^{\operatorname{bit}_{dn}})\)!(上面的\(dn\)表示在\(n\)前面放一个\(d\)

这个规律的提出在大刘的蓝书上也有涉及,并且可以用归纳法证明之,这里不再赘述。

所以接下来的流程就出来了,我们对于每一位,如果可以用这个规律刷出下一位就直接跳,否则(就是用规律算出前导零的情况)再枚举这一位的取值。

实际应用下在这个trick的优化下,再加上玄学的\(O(1)\)快速乘,可以跑的非常快(\(200ms\)过了\(1600\)组数据)。

CODE

#include<cstdio>
#define RI register int
typedef long long LL;
const LL lim=1e11,R=(1LL<<20)-1; int n,cases;
LL quick_mul(LL x, LL y, LL mod)
{
    return (x *(y>>20)%mod*(1LL<<20)%mod+x*(y&(R))%mod)%mod;
}
inline LL quick_pow(LL x,LL p,LL mod,LL mul=1)
{
    for (;p;p>>=1,x=quick_mul(x,x,mod)) if (p&1) mul=quick_mul(mul,x,mod); return mul;
}
inline bool expand(int idx,LL n,LL p,LL mod)
{
    int t; LL nxt; while (idx<12) if ((nxt=quick_pow(n,p,10LL*mod))!=p) p=nxt,++idx,mod*=10LL; else break;
    if (idx==12&&quick_pow(n,p,mod)==p) return printf("%lld\n",p),1; return 0;
}
inline bool DFS(int idx,LL p,LL mod)
{
    if (idx==12) { if (p>=lim&&quick_pow(n,p,mod)==p) return printf("%lld\n",p),1; return 0; }
    if (quick_pow(n,p,mod)==p&&expand(idx,n,p,mod)) return 1;
    for (RI i=0;i<10;++i) if (quick_pow(n,1LL*i*mod+p,mod)==p&&DFS(idx+1,1LL*i*mod+p,10LL*mod)) return 1; return 0;
}
int main()
{
    //freopen("CODE.in","r",stdin); freopen("CODE.out","w",stdout);
    while (scanf("%d",&n),n)
    {
        printf("Case %d: Public Key = %d Private Key = ",++cases,n);
        for (RI i=0;i<10;++i) if (DFS(1,i,10)) break;
    }
    return 0;
}

UVA12253 【简单加密法 Simple Encryption】

原文:https://www.cnblogs.com/cjjsb/p/10289897.html

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