[USACO1.2] 回文平方数 Palindromic Squares 题目解析

洛谷P1206 [USACO1.2] 回文平方数 Palindromic Squares 题目解析

题目描述

回文数是指从左向右念和从右向左念都一样的数。如 12321 12321 12321 就是一个典型的回文数。

给定一个用十进制表示的正整数 B B B，输出所有 [ 1 , 300 ] [1,300] [1,300] 中，它的平方用 B B B 进制表示时是回文数的数。

输入格式

共一行，一个单独的正整数 B B B。

输出格式

每行两个 B B B 进制的符合要求的数字，第二个数是第一个数的平方，且第二个数是回文数。

注意大于 9 9 9 的数，用字母表示。如用 A 表示 10 10 10，B 表示 11 11 11，用第 n n n 个大写字母表示 n + 9 n+9 n+9。

样例 #1

样例输入 #1

10

样例输出 #1

1 1
2 4
3 9
11 121
22 484
26 676
101 10201
111 12321
121 14641
202 40804
212 44944
264 69696

提示

【数据范围】
对于 100 % 100\% 100% 的数据， 2 ≤ B ≤ 20 2 \le B \le 20 2≤B≤20

题目翻译来自NOCOW。

USACO Training Section 1.2

解析

认真读题！认真读题！认真读题！重要的事情说三遍。

一道模拟题，解决步骤如下：

1. 转换数字到制定的进制：定义函数，将数字转换为 B B B 进制，在代码中该函数为 z h u a n ( ) , z h u a n 1 ( ) zhuan(),zhuan1() zhuan(),zhuan1()。

2. 判断回文：定义一个函数，检查是否是回文，在代码中该函数为 h u i w e ( ) huiwe() huiwe()。

3. 遍历 1 1 1 到 300 300 300：对每个数字，计算其平方，并将该数及其平方转换为 B B B 进制，检查平方是否是回文，如果是，则输出这个数及其平方（注意都是 B B B 进制下的数值，开始因为这个错了 ^_）。

代码如下：

#include<bits/stdc++.h>
using namespace std;

int b;
vector<int> v;
vector<int> v1;

void zhuan(int n) {
    while(n) {
        v.push_back(n%b);
        n=n/b;
    }
}

void zhuan1(int n) {
    while(n) {
        v1.push_back(n%b);
        n=n/b;
    }
}

bool huiwen(int n) {  //判断回文
    for(int i=0;i<v.size();i++) {
        if(v[i]!=v[v.size()-i-1]) return false;
    }
    return true;
}

int main() {
    cin>>b;
    for(int i=1;i<=300;i++) {
        v.clear(); v1.clear();
        int k=i*i;
        zhuan(k); zhuan1(i);
        if(huiwen(k)) {
            for(int j=v1.size()-1;j>=0;j--) {
                if(v1[j]>=10) {
                    cout<<char(v1[j]%10+65); //输出，注意大于 10 进制时的处理
                } else {
                    cout<<v1[j];
                }
            }
            cout<<" ";
            for(int j=0;j<v.size();j++) {
                if(v[j]>=10) {
                    cout<<char(v[j]%10+65);
                } else {
                    cout<<v[j];
                }
            }
            cout<<endl;
        }        
    }
    return 0;
}