LA 4998简单加密游戏 —— 自相似性质&&不动点迭代

题意

输入正整数 $K_1$（$K_1 \leq 50000$），找一个12为正整数 $K_2$（不能含有前导0）使得 ${K_1}^{K_2} \equiv K_2(mod \ {10}^{12})$。例如 $K_1=99$，$K_2=817 \ 245\ 479\ 899\ $.

分析

1、利用自相似性质

如果 ${K_1}^{K_2} \equiv K_2(mod \ {10}^{12})$，那么有 ${K_1}^{K_2 \% {10}^i} \equiv K_2\% {10}^i(mod \ {10}^{i}), \ i \leq 12$.

因此可以dfs从后往前一位一位得到。

考虑到不能含有前导0，可以求到13位，并要求大于等于1e12，答案再模1e12，这样就不会出现前导0.

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 1e12;

ll K1, K2;

ll w[], ans;

ll quickmul(ll a,ll b,ll mod) {

    ll ite = (1LL<<)-;

    return (a*(b>>)%mod*(1ll<<)%mod+a*(b&(ite))%mod)%mod;

}

ll qpow(ll a, ll b, ll mod)

{

    ll ret = ;

    while(b)

    {

        if(b&)  ret = quickmul(ret, a, mod);

        a = quickmul(a, a, mod);

        b >>= ;

    }

    return ret;

}

bool dfs(int cur, ll now)

{

    if(cur == )

    {

        if(now >= w[]){ans = now; return true;}

        return false;

    }

    ll W = w[cur];

    for(int i = ;i <= ;i++)

    {

        ll tmp = W*i + now;

        if(qpow(K1, tmp, W) == (tmp%W))

        {

            if(dfs(cur+, tmp))  return true;

        }

    }

    return false;

}

int main()

{

    int kase = ;

    w[] = ;

    for(int i = ;i < ;i++)  w[i] = w[i-] * ;

    while(scanf("%lld", &K1) ==  &&K1)

    {

        dfs(, );

        printf("Case %d: Public Key = %lld Private Key = %lld\n", ++kase, K1, ans%mod);

    }

}

2、不动点迭代

初始时随机选取一个超过10^12的数，如1000000000007，将其代入计算，如果f(x)!=x，那么令x=f(x)，如此循环，能在短时间内找出合法解。

#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

const ll mod = 1e12;

ll K1, K2;

ll quickmul(ll a,ll b,ll mod) {

    ll ite = (1LL<<)-;

    return (a*(b>>)%mod*(1ll<<)%mod+a*(b&(ite))%mod)%mod;

}

ll qpow(ll a, ll b, ll mod)

{

    ll ret = ;

    while(b)

    {

        if(b&)  ret = quickmul(ret, a, mod);

        a = quickmul(a, a, mod);

        b >>= ;

    }

    return ret;

}

int main()

{

    int kase = ;

    while(scanf("%lld", &K1) ==  &&K1)

    {

        K2 = 1e11+;

        while(qpow(K1, K2, mod) != K2%mod)  K2 = qpow(K1, K2, mod);

        printf("Case %d: Public Key = %lld Private Key = %lld\n", ++kase, K1, K2);

    }

}

参考链接：

1. http://www.bubuko.com/infodetail-587732.html

2. https://blog.csdn.net/w4149/article/details/77750279

巴特西

LA 4998简单加密游戏 —— 自相似性质&&不动点迭代

题意

分析

最新文章

热门文章