2019.7.7 校内测试题 尴尬的密码员

　

题目

　　尴尬的密码员(crypto.cpp,128MB,1s)

【问题描述】:

　　年轻有为的密码员小 Y 已经成功为他现在的公司中一个拥有成千上万用户

的大系统设计了一套加密模块。这个加密模块的密码是由两个素数的乘积产生，

小 Y 确信这个密码很安全，因为还没有一种有效的方法对这样的乘积进行因数

分解。

　　然后小 Y 没有想到的是，密码的两个因数都应该是很大的，而不仅仅只要

它们的乘积大。现在可以认为某些用户的密码是弱密钥。为了不被解雇，小 Y

秘密地浏览所有用户的密码，检查它们是否足够强大，当然尤其要特别小心的检

查老板的密钥。

【输入文件】:　

　　输入包含不超过 20 组的测试数据，每行一个测试数据含有两个整数 K 和 L

（4 <= K <= 10^100、2 <= L <= 10^6），K 表示是由两个素数乘积得到的密码，L

是破解密码者最想要密码最小因数的范围，输入由 K=0 L=0 结束。

【输出文件】:

　　对于每一个密码 K，如果它的最小一个因数 p<l< span="">，就输出”BAD p”；否则就

输出”GOOD”，每个测试数据输出一行。

【样例】

【输入输出样例】：

　　

　　crypto.in

　　　　143 10

　　　　143 20

　　　　667 20

　　　　667 30

　　　　2573 30

　　　　2573 40

　　　　0 0

　　crypto.out

　　　　GOOD

　　　　BAD 11

　　　　GOOD

　　　　BAD 23

　　　　GOOD

　　　　BAD 31　　

【数据规模】:

　　　　如上

考试得分：　　50

主要算法 ：　　质数（质因数分解，欧拉素数筛）

 

题干：

　　　　将一个超大合数化为两个最小质数的乘积，求出其中最小的质数

应试策略：

　　1.枚举2-L中的质数

　　2.如果K/（枚举的数）为质数的话，输出答案

　　 代码

#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#define LL long long
#define FORa(i,s,e) for(LL i=s;i<=e;i++)
#define FORs(i,s,e) for(LL i=s;i>=e;i--)
#define gc pa==pb&&(pb=(pa=buf)+fread(buf,1,10000,stdin),pa==pb)?EOF:*pa++
#define File(name) freopen(name".in","r",stdin),freopen(name".out","w",stdout)

using namespace std;
static char buf[10000],*pa=buf,*pb=buf;
inline LL read();

LL K,L;
bool Prime(int x)
{
    FORa(i,2,sqrt(x))
        if(x%i==0)
            return 0;
    return 1;
}
void Solve()
{
    FORa(i,2,L-1)
    {
        if(Prime(i)&&Prime(K/i)&&K%i==0)
        {
            printf("BAD %d
",i);
            return; 
        }
    }
    printf("GOOD
");
}
int main()
{
    File("crypto");
    K=read(),L=read();
    while(K!=0&&L!=0)
    {
        Solve();
        K=read(),L=read();
    }
    return 0;
}
inline LL read()
{
    register LL x(0);register LL f(1);register char c(gc);
    while(c<'0'||c>'9') f=c=='-'?-1:1,c=gc;
    while(c>='0'&&c<='9') x=(x<<1)+(x<<3)+(c^48),c=gc;
    return x*f;
}

非完美算法：　　

　　　　照搬应试策略

正解：

　　1.欧拉素数筛，质数算术基本定理

　　2.求出2-L内的最小的质数，运用高精看K是否可以整除这个质数，可以就是答案

　　代码

　

#include<math.h>
#include<stdio.h>
#include<stdlib.h>
#include<iostream>
#include<cstring>
#define LL long long
#define FORa(i,s,e) for(LL i=s;i<=e;i++)
#define FORs(i,s,e) for(LL i=s;i>=e;i--)
#define File(name) freopen(name".in","r",stdin);freopen(name".out","w",stdout);

const int N=1000000;
int cnt,prime[N+1],v[N+1];
string K;
LL L;
void Prime()
{
    FORa(i,2,L)
    {
        if(!v[i]) v[i]=prime[++cnt]=i;
        FORa(j,1,cnt)
        {
            if(prime[j]>j|prime[j]*i>L) break;
            v[prime[j]*i]=prime[j];
        }
    }
}
bool Check(int x)
{
    int f=1;
    while(1);
}
void Solve()
{
    FORa(i,1,cnt)
    {
        if(Check(i))
        {
            printf("BAD %d
",i);
            return; 
        }
    }
    printf("GOOD
");
}
int main()
{
    File("crypto");
    while(K!="0"&&L!=0)
    {
        Prime(),Solve();
        cin>>K;
        scanf("%d",&L);
    }
    return 0;
}

总结：

　　欧拉素数筛类板子