Gift From the Gods 题解

· · 题解

Gift From the Gods 题解

题目传送门

本题解你可以学到：reverse 函数，预处理的思想，如何判断回文，和如何判断质数。

大模拟。

Part 1 题意理解

题目简述：

疯狂给定一个整数 a，满足 1 \le a\le 1\times 10^6，输出 2\times a，直到 a 是一个回文质数时，停止程序。（给定数据中也可以没有回文质数）

1、首先我们考虑如何判断一个数是否为回文数：

因为万能的 STL 中给出了一个万能的函数：

reverse();

其作用是将 string 类、vector 类等的顺序颠倒过来，如，一个 string 类型的变量 str 中储存着以下的数据： 

abcdefg

在使用了 reverse 后，str 中的数据变成了：

gfedcba

其中 reverse 的使用格式为：

reverse(str.begin(),str.end());

（其他 reverse 的使用方法你们可以自己查一查）

所以，我们可以将一个数字转换成字符串后再翻转，判断翻转后的字符串是否和原字符串相等，现在我们的问题是：如何将一个数字转换成字符串类？

string ans;
while(num){
    ans=(char)((num%10)+'0')+ans;
    num/=10;
}

上面的代码中，我们每次将 num 的最后一位取出，强制转化为 char 类后加在 ans 之前。string 类也能有加法？没错，string 允许字符串相加，如：

"ab"+"cd"="abcd"

现在，我们解决了如何判断一个数为回文数的问题。

2、如何判断一个数是质数？

众所周知，质数是指除了 1 外，那些因数只有 1 和它本身的数（ 1 既不是质数，也不是合数）。所以我们可以用以下代码检验一个数是否为质数：


bool is(ll num){
    if(num<=1)//1 和 0 不是质数
    for(int i=2;i<=sqrt(num);i++)//只用从2枚举到sqrt(num)，想想是为什么 
        if(num%i==0)return false;//如果有除了1和本身的因数，就说明不是质数 
    return true;//只有1和它本身是它的因数，是质数 
}

上述代码比较基础，时间复杂度为 O(\sqrt {num})。

如果有 n 次询问，则复杂度为 O( \sum^n_{i=1}\sqrt{num_i})。

我们考虑预处理，让查询是否为质数的时间为 O(1)，但预处理的复杂度为 O(maxn)。这样 O(maxn) 的复杂度在大数据中可以比 O( \sum^n_{i=1}\sqrt{num_i}) 好，小数据中也能过。虽然这个处理在本题中没多大用，但是在一些需要重复运算得答案的题目中，预处理就显得尤为重要。下面的代码展示了欧拉筛筛质数的方法，时间为 O(maxn)。


void sieve(){
    f[1]=true;//1不是质数
    for(int i=2;i<=(ll)1e6;i++){//1e6就是1倍10的6次方的意思
        if(!f[i])pre[++top]=i;
        for(int j=1;j<=top and i*pre[j]<=(ll)1e6;j++){
            f[i*pre[j]]=true;
            if(i%pre[j]==0)break;
        }
    }
}

其中 f_i 为真，表示 i 不为质数；pre 数组中存了所有的质数。

Part 2 代码

上文有解释了，就不多讲了。

#include<bits/stdc++.h>
#define ll long long
using namespace std;
ll a;
bool f[(ll)2e6+15];
ll pre[(ll)1e6+15],top;
bool work(ll num){
    if(f[num])return false;//如果 num 不是质数，直接结束。
    string ans;
    while(num){//数字转换成字符串
        ans=(char)((num%10)+'0')+ans;
        num/=10;
    }
    string temp=ans;
    reverse(ans.begin(),ans.end());
    return temp==ans;
}
void sieve(){//欧拉筛
    f[1]=true;
    for(int i=2;i<=(ll)1e6;i++){
        if(!f[i])pre[++top]=i;
        for(int j=1;j<=top and i*pre[j]<=(ll)1e6;j++){
            f[i*pre[j]]=true;
            if(i%pre[j]==0)break;
        }
    }
}
int main(){
    ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);//关闭同步流，使得cin，cout的速度和printf和scanf差不多。加了这句话后，不能再用printf和scanf了。
    sieve();
    while(cin>>a){//疯狂读入，在本地调试时，如果手打数据，程序不知道什么时候截止，就会死循环执行这一句话。可以用文件输入解决这个问题。
        bool flag=work(a);
        cout<<a*2<<'\n';
        if(flag)return 0;
    }
    return 0;
}

这种小众的题目非常简单，写出来的题解可能根本没有人看，但是，一个简单的题目中也能提炼出很多有用的东西。如果哪一天能帮助一个人，那这就是我写的题解的意义所在（试图为自己简单事情复杂化开脱）。如果这篇题解有帮到你，留个赞吧，谢谢。