D - Happy Happy Prime Prime

题意:
给出一个数,判断这个数是质数并且一直迭代它的平方和直到它能变成1,如果是输出“YES”,否则输出“NO”.

题解:
先筛素数,再处理即可

代码:

#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <cctype>
#include <map>
#include <set>
#include <vector>
#include <string>
#include <stack>
#include <queue>

#define lowbit(x) x & (-x)
#define lson left,mid,root << 1
#define rson mid+1,right,root << 1 | 1

using namespace std;

typedef pair<int, int> PII;
typedef long long ll;
typedef unsigned long long ull;
const ll mod=1e9+7;
const ll inf=0x3f3f3f3f;
const double pi=acos(-1.0);
const double eps=1e-8;
const int maxn=1e4+100;

bool vis[maxn];
int vis2[maxn];
int prime[maxn];
int cnt;
int f;

void getprime()
{
  vis[1] = true;
  for(int i = 2; i <= maxn; i ++)
      {
        if(!vis[i])
            prime[cnt ++] = i;
        for(int j = 0; prime[j] <= maxn / i; j ++)
            {
              vis[i * prime[j]] = true;
              if(i % prime[j] == 0)
                  break;
            }
      }
}

void dfs(int x)
{
  if(x == 1 || x == 7)
      {
        f = 1;
        return ;
      }
  if(x < 10)
    return ;
  int sum = 0;
  while(x)
        {
          sum += (x % 10) * (x % 10);
          x /= 10;
        }
  dfs(sum);
}


int main()
{
  getprime();
  int t;
  int p;
  int x;
  scanf("%d",&t);
  while(t --)
        {
          scanf("%d%d",&p,&x);
          printf("%d %d ",p, x);
          if(vis[x])
            puts("NO");
          else
            {
              f = 0;
              dfs(x);
              if(f)
                 vis2[x] = 1;
              else
                 vis2[x] = 0;
              if(vis2[x])
                puts("YES");
              else
                puts("NO");
            }
        }
   return 0;
}

点赞

发表评论

电子邮件地址不会被公开。必填项已用 * 标注