【藍橋杯】2013-A組02 排它平方數

• 2020 年 2 月 13 日
• 筆記

題目描述：

小明正看着 203879 這個數字發獃。原來，203879 * 203879 = 41566646641。這有什麼神奇呢？仔細觀察，203879 是個6位數，並且它的每個數位上的數字都是不同的，並且它平方後的所有數位上都不出現組成它自身的數字。具有這樣特點的6位數還有一個，請你找出它！再歸納一下篩選要求：1. 6位正整數；2. 每個數位上的數字不同；3. 其平方數的每個數位不含原數字的任何組成數位。答案是一個6位的正整數。

解題思路：

首先無腦枚舉找出每個數位上數字不同的6位正整數，然後用bool型函數check來檢查數字y中是否每個數位出現的數字在x中都不曾出現過，這一步可以用自定義函數ll2s來把long long型的數字轉換成string型再用find進行查找，最後輸出即可。

AC代碼：

#include <bits/stdc++.h>  using namespace std;  #define Up(i,a,b) for(int i = a;i <= b; i++)  typedef long long ll;    void ll2s(ll x,string &str)  //把long long轉換成string  {      stringstream ss;      ss << x;      ss >> str;  }    bool check(ll x,ll y)  //檢查y中是否含有x中的數字  {      string strx,stry;      ll2s(x,strx);      ll2s(y,stry);      Up(i,0,strx.length()-1)      {          if(stry.find(strx[i]) != string::npos)          {              return false;          }      }      return true;  }    int main()  {      ios::sync_with_stdio(false);      cin.tie(0),cout.tie(0);      Up(i,1,9)      {          Up(j,0,9)          {              if(i!=j)              {                  Up(k,0,9)                  {                      if(k!=i && k!=j)                      {                          Up(l,0,9)                          {                              if(l!=i && l!=j && l!=k)                              {                                  Up(m,0,9)                                  {                                      if(m!=i && m!=j && m!=k && m!=l)                                      {                                          Up(n,0,9)                                          {                                              if(n!=i && n!=j && n!=k && n!=l && n!=m)                                              {                                                  ll x = i*1e5+j*1e4+k*1e3+l*1e2+m*10+n;                                                  ll y = x*x;                                                  if(check(x,y) && x!=203879) cout << x << endl;                                              }                                          }                                      }                                  }                              }                          }                      }                  }              }          }      }      return 0;  }