问题 1821: [蓝桥杯][2014年第五届真题]拼接平方数

时间限制: 1Sec 内存限制: 128MB 提交: 35 解决: 18

题目描述

小明发现49很有趣，首先，它是个平方数。它可以拆分为4和9，拆分出来的部分也是平方数。169也有这个性质，我们权且称它们为：拼接平方数。

100可拆分1 00，这有点勉强，我们规定，0 00 000 等都不算平方数。

小明想：还有哪些数字是这样的呢？

你的任务出现了：找到某个区间的所有拼接平方数。

输入

两个正整数 a b (a<b<10^6)

输出

若干行，每行一个正整数。表示所有的区间[a,b]中的拼接平方数

样例输入

1 200

样例输出

49
169

提示
无
来源
无

题目解析

这一题属于上周，我们实验室进行考核的一道题目，由于上一道题目关于字符串的，耗了很长的时间，导致最后一些简单的题目都没有做出来。。。。

当时看这个题目的时候并没有思路，但是现在看的时候感觉还好吧(其实自己想了很久的QAQ)

代码解析

这里的拼接平方数是完全平方数的一种特殊情况，要求求出的数本身是完全平方数，并且要求存在对数的一种划分，使得两部分都是完全平方数，且不为0。

#include<bits/stdc++.h>
using namespace std;
int getDigit(int n) {  //求一个正整数n的位数
    int num=n;
    int digit=0;
    while(num) {
        digit++;
        num/=10;
    }
    return digit;
}
int is_pownum(int n) { //判断正整数n是否是完全平方数
    int temp;
    temp=sqrt(n);
    if(temp*temp==n)
        return 1;
    else
        return 0;
}
int main() {
    int a,b;
    int i,j,k;
    int n,n1,n2,suc;   //n1.n2-数n的两部分 n-拼接后的数 suc-拼接平方数判断标记
    scanf("%d %d",&a,&b);
    for(i=a; i<=b; i++) {
        if(!is_pownum(i))  //如果区间[a,b]内的某个数i不是完全平方数，直接返回，不再判断
            continue;
        suc=0; //是完全平方数，置标记suc=0
        for(j=1; j<getDigit(i); j++) { //求n1与n2
            n=i;
            n1=0,n2=0;
            for(k=1; k<=j; k++) {   //n1最少1位，最多getDigit(i)位，并且要含上可能出现的0
                n1+=((n%10)*pow(10,k-1));
                n/=10;
            }
            n2=(i-n1)/pow(10,j);//n2=n1未包含的数位对应的数字
            if(is_pownum(n1) && is_pownum(n2) && n1!=0 && n2!=0) { //n1 n2均为完全平方数且均不为0（排除0 00 000等情况）
                suc=1;  //置标记suc=1，说明找到符合条件的拼接平方数，并退出所有循环
                break;
            }
        }
        if(suc)
            printf("%d\n",i);
    }
    return 0;
}

还有一个大佬另一种写法

分成两部分，如果两部分都死平方数，返回true

#include<bits/stdc++.h>
using namespace std;
bool ccc(int i) {
    int s = sqrt(i);
    if(s*s==i)
        return true;
    return false;
}
bool check(int n) {
    int flag[8]= {0},i=0;
    while(n) {
        flag[i++]=n%10;
        n/=10;
    }
    int j,k=i-1;
    int s=0,s2=0;
    for(i--; i>0; i--) {
        s+=flag[i];
        if(!ccc(s)) { //如果当前不是平方数，继续往后加
            s*=10;
            continue;
        }
        //如果当前是平方数，判断后半段
        for(j=i-1; j>=0; j--) {
            s2+=flag[j];
            if(j==0)
                continue;
            s2*=10;
        }
        if(s2==0)
            continue;

        if(ccc(s2)) {
            return true;
        }
        s2=0;
        s*=10;
    }
    return false;
}
int main() {
    int x,y;
    cin>>x>>y;
    for(long i=x; i<=y; i++) {
        if(ccc(i)) {
            //cout<<i<<"  "<<s<<endl;
            if(check(i))
                cout<<i<<endl;
        }
    }
    return 0;
}