5

POJ 2635 - The Embarrassed Cryptographer

 2 years ago
source link: https://exp-blog.com/algorithm/poj/poj2635-the-embarrassed-cryptographer/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
neoserver,ios ssh client
The Embarrassed Cryptographer

给定一个大数K，K是两个大素数的乘积的值。

再给定一个int内的数L

问这两个大素数中最小的一个是否小于L，如果小于则输出这个素数。

首先对题目的插图表示无语。。。

高精度求模+同余模定理，解题步骤：

1、 Char格式读入K。把K转成千进制Kt，同时变为int型。

把数字往大进制转换能够加快运算效率。若用十进制则耗费很多时间，会TLE。

千进制的性质与十进制相似。

例如，把 K=1234567890 转成千进制，就变成了： Kt=[ 1][234][567][890] 。

为了方便处理，我的程序是按“局部有序，全局倒序”模式存放 Kt

即 Kt=[890][567][234][1 ] (一个中括号代表一个数组元素)

2、 素数打表，把10^6内的素数全部预打表，在求模时则枚举到小于L为止。

注意打表不能只打到100W，要保证素数表中最大的素数必须大于 10^6，否则当 L=100W 且K为 GOOD 时，会因为数组越界而RE，这是因为越界后prime都是负无穷的数，枚举的 while(prime[pMin]<L) 循环会陷入死循环

3、 高精度求模。

主要利用Kt数组和同余模定理。

例如要验证123是否被3整除，只需求模 124%3

但当123是一个大数时，就不能直接求，只能通过同余模定理对大数“分块”间接求模

具体做法是：

  • 先求 1%3 = 1
  • 再求 (1*10+2)%3 = 0
  • 再求 (0*10+4)%3 = 1

那么就间接得到 124%3=1，这是显然正确的

而且不难发现， (1*10+2)*10+4 = 124

这是在10进制下的做法，千进制也同理，*10 改为 *1000 就可以了

//Memory Time
//624K  1235MS 

#include<iostream>
#include<string.h>
using namespace std;

const int Range=1000100;  //打表不能只打到100W，素数表中最大的素数必须大于10^6

int Kt[10000];  //千进制的K
int L;
int prime[Range+1];

/*素数组打表*/
void PrimeTable(void)
{
    int pNum=0;
    prime[pNum++]=2;

    for(int i=3;i<=Range;i+=2)  //奇偶法
    {
        bool flag=true;
        for(int j=0;prime[j]*prime[j]<=i;j++)  //根号法+递归法
            if(!(i%prime[j]))
            {
                flag=false;
                break;
            }
        if(flag)
            prime[pNum++]=i;
    }
    return;
}

/*高精度K对p求模，因数检查(整除)*/
bool mod(const int* K,const int p,const int len)
{
    int sq=0;
    for(int i=len-1;i>=0;i--)  //千进制K是逆序存放
        sq=(sq*1000+K[i])%p;  //同余模定理

    if(!sq)   //K被整除
        return false;
    return true;
}

int main(void)
{
    PrimeTable();

    char K[10000];
    while(cin>>K>>L && L)
    {
        memset(Kt,0,sizeof(Kt));
        int lenK=strlen(K);
        for(int i=0;i<lenK;i++)  //把K转换为千进制Kt，其中Kt局部顺序，全局倒序
        {                      //如K=1234567=[  1][234][567] ，则Kt=[567][234][1  ]
            int pKt=(lenK+2-i)/3-1;
            Kt[pKt]=Kt[pKt]*10+(K[i]-'0');
        }
        int lenKt=(lenK+2)/3;

        bool flag=true;
        int pMin=0;  //能整除K且比L小的在prime中的最小素数下标
        while(prime[pMin]<L)  //枚举prime中比L小的素数
        {
            if(!mod(Kt,prime[pMin],lenKt))
            {
                flag=false;
                cout<<"BAD "<<prime[pMin]<<endl;
                break;
            }
            pMin++;
        }
        if(flag)
            cout<<"GOOD"<<endl;
    }
    return 0;
}

report

Recommend

About Joyk


Aggregate valuable and interesting links.
Joyk means Joy of geeK