题目地址:https://pintia.cn/problem-sets/994805046380707840/problems/1111914599412858886
题目:
解题思路:
第一遍模拟确定哪些数是特立独行的数,如果是则re[]值置为0
注意,对于x(A≤x≤B),在它的迭代过程中设置一个vis[]数组来判读出现死循环的情况,如果出现死循环则re[x]=1.
且在迭代过程中,除了最初的x,其他后续迭代的数都是依赖x的,它们的re[]也应该置为1
对于特立独行的数进行第二遍模拟,确定独立性。不会超时,数据量还是比较小的
比赛的时候感觉心态不太好,有点太看重分数了,也有点受到彩虹糖那道题的影响(一直没改对,虽然感觉逻辑没问题)
佛系一点也挺好,也许这道题当场就能做出来了呢!Keep Learning٩(˃̶͈̀௰˂̶͈́)و
ac代码:
#include <iostream>
#include <algorithm>
#include <string.h>
#include <ctype.h>
#include <set>
#include <cmath>
#include <queue>
#include <stack>
#include <map>
#include <sstream>
#define maxn 10005
typedef long long ll;
const ll inf=99999999;
using namespace std;
int re[maxn]={0};
bool isprime(int x)
{
int t=sqrt(x);
for(int i=2;i<=t;i++)
if(x%i==0)
return false;
return true;
}
int main()
{
//freopen("/Users/zhangkanqi/Desktop/11.txt","r",stdin);
int a,b;
scanf("%d %d",&a,&b);
for(int x=a;x<=b;x++)
{
int t=x;
if(!re[x]) //目前这个值不依赖
{
int vis2[maxn]={0};
while (1)
{
int tmp=0;
while (x)
{
tmp += (int) pow((x % 10), 2);
x /= 10;
}
x = tmp;
if(x==1) break;
re[x]=1;//迭代出来的数都不是独立的
if(vis2[x])//死循环
{
re[x]=1;
re[t]=1;
break;
}
vis2[x]=1;//标记迭代内出现的数
}
}
x=t;
}
int c=0;
for(int x=a;x<=b;x++)
{
int t=x;
if(!re[x])//不依赖
{
int num=0,res=x;
if(isprime(x))
c=2;
else
c=1;
while(x!=1)
{
num++;
int tmp=0;
while (x)
{
tmp += (int) pow((x % 10), 2);
x /= 10;
}
x=tmp;
}
printf("%d %d\n",res,c*num);
}
x=t;
}
if(c==0)
printf("SAD");
return 0;
}