UVa - 1017. Staircases 动态规划法 题解

本文出自：http://blog.csdn.net/svitter，转载请注明出处。

原题：点击打开链接

和晨阳哥一同讨论了一下这个题目= =终于在今晚AC了。

这个题目可以说是RSA加密算法的变种。。

考虑997是素数，那么符合欧拉定理，然后想到费马小定理 m ^ 996 MOD 997 = 1;

因为一般的RSA解密算法都是C^d mod 997 = m 这种形式，苦思冥想了好久解密算法，仍然没有得到解决。

最后终于大彻大悟的明白：

呵呵，你想多了。。这个题目可以用打表过- -

要注意的问题：

1.加密码与原码是要一一对应，在原码中已经标出。

2.计算MOD幂的时候使用二分算法，如果不使用必然超时（n 可以取到  10 ^ 9)。这个算法依据pow算法得出。

/*author : Vit/csdn   
 *from: http://blog.csdn.net/svitter  
 *if you love it, please show the original site*/  


#include <iostream>
#include <stdio.h>
#include <string.h>

using namespace std;

#define lln long long int

char str[1000010];
char key[1001];
lln ch[127];
lln n;
lln ans, tt, temp;

bool get(lln &c)
{
    temp = c, ans = 1, tt = n;
    while(tt)
    {
        if(tt &1)
            ans = (ans * temp) % 997;
        temp = temp * temp % 997;
        tt = tt >> 1;
    }
    if(ch[c] == -1)
        ch[c] = ans;
}

bool init()
{
    lln i;
    memset(ch, -1, sizeof(ch));
    memset(key, ‘\0‘, sizeof(key));
    for(i = 32; i < 127; i++)
    {
        if(get(i))
            continue;
        else
            return false;
    }

    for(i = 32; i < 127; i++)
    {
        lln &tmp = ch[i];
        if(key[tmp] == ‘\0‘)//检查码值相同的情况
            key[ch[i]] = (char)i;
        else
        {
            return false;
        }
    }
    return true;
}

void ace()
{
    lln c, cur;
    lln length;
    lln i, l;
    char temp[400000];
    bool isstr;
    cin >> c;
    while(c--)
    {
        while(cin >> n)
        {
            memset(str, ‘\0‘, sizeof(str));
            scanf("%s", str);
            if(init())
            {
                l = 0;
                isstr = 1;
                //cout << key[590] << endl;
                length = strlen(str);
                for(i = 0; i < length; i += 3)
                {
                    cur = (str[i]-‘0‘) *100 + (str[i+1]-‘0‘) * 10 + str[i+2] - ‘0‘;
                    if(key[cur] != ‘\0‘)//没有对应的翻译码
                        temp[l++] = key[cur];
                    else
                    {
                        isstr = false;
                        break;
                    }
                }
                if(isstr)
                {
                    for(i = 0; i < l; i++)
                        cout << temp[i];
                    cout << endl;
                }
                else
                {
                    cout << "No Solution" << endl;
                }
            }
            else
            {
                cout << "No Solution" << endl;
            }
        }
    }
}

int main()
{
    ace();
    return 0;
}

UVa - 1017. Staircases 动态规划法 题解,布布扣,bubuko.com

UVa - 1017. Staircases 动态规划法 题解

原文：http://blog.csdn.net/kenden23/article/details/24270283