首页 > 代码库 > UVALive 4998 Simple Encryption

UVALive 4998 Simple Encryption

2024-09-12 06:22:25   216人阅读

题目描述：

　　输入正整数K1（K1<=5000）,找一个12位正整数K2使得K1K2=K2(mod 1012)。

解题思路：

　　压缩映射原理：设X是一个完备的度量空间，映射?:Χ→Χ 把每两点的距离至少压缩λ倍，即d（?（x），?(y))≤λd(x,y)，这里λ是一个小于1的常数，那么?必有而且只有一个不动点,而且从Χ的任何点x0出发作出序列x1=?（x0），x2=?（x1），...，xn=?（x(n-1)），...，这序列一定收敛到那个不动点。

　　题目要求解的方程形式是f(K2)=K2,很直接地就想到不动点原理。

　　另外，K2的值较大，在求解K1K2(mod 1012)时要利用矩阵快速幂，同时由于是对1012取模，两个1012级别的数相乘结果会爆long long，所以在做乘法时要用到O(1)快速乘。

 

代码如下：

#include<bits/stdc++.h>
using namespace std;

typedef  long long ll;

const ll MOD=1e12;

ll mul(ll a,ll b)
{
    ll ite=(1ll<<20)-1;
    return (a*(b>>20)%MOD*(1<<20)%MOD+a*(b&ite)%MOD)%MOD;
}

ll pow_mod(ll a,ll b)
{
    ll ret=1;

    while(b)
    {
        if(b&1)
            ret=mul(ret,a)%MOD;

        b>>=1;
        a=mul(a,a)%MOD;
    }
    return ret;
}


ll solve(ll n)
{
    ll x=1e12;
    while(1)
    {
        ll ans=pow_mod(n,x);
        if(ans==x)
            return ans;

        x=ans;
    }
}

int main()
{
    ll k1;
    int Case=0;
    while(scanf("%lld",&k1)&&k1)
    {
        ll k2=solve(k1);
        printf("Case %d: Public Key = %lld Private Key = %lld\n",++Case,k1,k2);
    }
    return 0;
}

 

　　

UVALive 4998 Simple Encryption


联系
我们