四位完全平方数

· · 个人记录

四位完全平方数

题意

求所有形如aabb的四位完全平方数

思路（聊天）

这题看起来很简单。实际上确实很简单

我们可以暴力去算，毕竟数据很小。 这个大概是我学循环结构时的练习题吧。

但是喜欢折腾的我就不会止步于此。（提供四个算法）

算法一：

我们可以从1000到9999直接枚举。

判断一个数是不是平方数比较简单，只要预处理一下就好了，看代码

const int N=9999+5;
int is[N];

int i;
memset(is,0,sizeof(is));
for(i=1;i*i<=9999;i++)
    is[i*i]=true;

然后，判断一个数是否是aabb的形式，可以这样

bool isaabb(int x)
{
    return (x/1000==(x/100)%10&&(x/10)%10==x%10);
}

然后就可以愉快的暴力了

/*···惯用模板···*/
#include<bits/stdc++.h>
using namespace std;
typedef unsigned long long ULL;
typedef long long LL;
template<class T>
inline void read(T &x)//快读
{
    x=0;char ch;bool f=true;
    while(((ch=getchar())<'0'||ch>'9')&&ch!='-');
    if(ch=='-')f=false,ch=getchar();
    for(;ch>='0'&&ch<='9';ch=getchar())
        x=(x<<1)+(x<<3)+ch-'0';
    if(!f)x=~x+1;
}
template<class T>
inline void write(T x)//快写
{
    T t=x;char c[25];int i=0;
    if(!t)putchar('0');
    if(t<0)putchar('-'),t=~t+1;
    while(t)c[++i]=t%10,t/=10;
    for(int j=i;j>0;j--)putchar(c[j]+48);
    putchar(' ');
}//快读快写似乎没有什么必要
const int N=9999+5;
/*···惯用模板···*/
int is[N];
bool isaabb(int x)//判断一个数是否是aabb的形式
{
    return (x/1000==(x/100)%10&&(x/10)%10==x%10);
}
int main()
{
    memset(is,0,sizeof(is));
    int i;
    for(i=1;i*i<=9999;i++)
        is[i*i]=true;//预处理平方数
    for(i=1000;i<=9999;i++)
        if(isaabb(i)&&is[i])write(i);//输出答案
    putchar(10);//习惯文末换行
    return 0;
}

循环次数为9000次。

算法二：

折腾开始---- 我们可以构造出形如aabb的数，然后再去判断是否是平方数。

for(int a=1;a<=9;a++)//注意此处a最小为1
    for(int b=0;b<=9;b++)
    {
        int n=a*1000+a*100+b*10+b;
        if(is[n])write(n);
    }

循环次数大大减少。（90次）

算法三

根据算法二，我们也很容易联想到算法三：枚举所有平方数，再判断是不是形如aabb。

for(i=30;i*i<=9999;i++)
    if(isaabb(i*i))
        write(i*i);

循环次数降到69次

前方高能！！！

终于到了展现思想成果的时候了！

我们从数学的角度来考虑优化。 形如aabb的平方数究竟有什么性质呢？？？

命题：若一个形如aabb的数是一个平方数，那么一定满足a+b=11.

证明：

若一个形如aabb的数为一完全平方数，那么这个数的平方根一定是整数。

n=\sqrt{1100a+11b}=\sqrt{11}\sqrt{100a+b}\in N

容易得到

11整除(100a+b) \frac{100a+b}{11}$=$9a+\frac{a+b}{11}

所以a+b=1或11

如果a+b=1，那么a=1,b=0，显然是不成立的，故原命题得证。

现在我们只要让b=11-a就好了！！！

for(int a=2;a<=9;a++)//若a=1，则b=10,这是不可能的
{
    int b=11-a;
    int n=1100*a+11*b;
    if(is[n])write(n);
}

我感觉这个优化似乎并没有卵用

第一篇终于打完了，LateX真的难打