1.2.4 USACO Palindromic Squares回文平方数数字与字符转换十进制转为任意进制

谁借莪１个温暖的怀抱￠ 2023-07-12 14:18 12阅读 0赞

**Palindromic Squares**  
Rob Kolstad

Palindromes are numbers that read the same forwards as backwards. The number 12321 is a typical palindrome.

Given a number base B (2 <= B <= 20 base 10), print all the integers N (1 <= N <= 300 base 10) such that the square of N is palindromic when expressed in base B; also print the value of that palindromic square. Use the letters 'A', 'B', and so on to represent the digits 10, 11, and so on.

Print both the number and its square in base B.

### PROGRAM NAME: palsquare ###

### INPUT FORMAT ###

A single line with B, the base (specified in base 10).

### SAMPLE INPUT (file palsquare.in) ###

### OUTPUT FORMAT ###

Lines with two integers represented in base B. The first integer is the number whose square is palindromic; the second integer is the square itself. NOTE WELL THAT BOTH INTEGERS ARE IN BASE B!

### SAMPLE OUTPUT (file palsquare.out) ###

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

翻译：[https://www.luogu.com.cn/problem/P1206][https_www.luogu.com.cn_problem_P1206]

## 题目描述 ##

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

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

## 输入格式 ##

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

## 输出格式 ##

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

注意大于 99 的数，用字母表示。如用 `A` 表示 1010，`B` 表示 1111，用第 nn 个大写字母表示 n+9n+9。

## 输入输出样例 ##

**输入 \#1**复制

**输出 \#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% 的数据，2 \\le B \\le 202≤B≤20

题目翻译来自NOCOW。

USACO Training Section 1.2

> 解析：对1-300的数字进行枚举，判断每一个数字的平方转成B进制后是否是回文数。如果是回文数，输出者数字转成B进制的值和这个数字的平方转成B进制的值。

/*
    ID: L 
    PROG: palsquare
    LANG: C++ 
    */ 
    #include<bits/stdc++.h> 
    using namespace std;
    bool huiwen(string s)//12321 判断是否为回文数 
    {
    	int n = s.length();
    	for(int i = 0; i <= n/2; ++i)
    	{
    		if(s[i] != s[n-i-1]) return false;
    	}
    	return true;
    }
    
    
    string ten_to_r(int n, int r)//将十进制的n转为r进制 
    {
    	char str[10005]={0};//记得要初始化，否则结果是错的 
    	stack<int> st;
    	while(n!=0)
    	{
    		st.push(n%r); 
    		n = n/r;
    	}
    	int i = 0;
    	while(!st.empty())//将数字转成字符 
    	{
    		int s = st.top();
    		if(s >= 10)	str[i++] = s - 10 + 'A';// 大于10的数字转成字符，比如11->B 12->C 
    		else str[i++] = s+'0';//小于10的数字转成字符 
    		st.pop();
    		//cout << str[i-1] <<" "<<i<<" "; 
    	}
    //	string ss = str;
    	return str;
    }
     
    string num_to_str(int n)//数字转字符 
    {
    	string res;
    	stringstream ss;
    	ss << n;//将数字n转成字符res 
    	ss >> res;//res = ss.str()
    	return res; 
    }
    
    int str_to_num(string s)//字符转数字 
    {
    	int res;
    	stringstream ss;
    	ss << s;
    	ss >> res;
    	return res;
    } 
    
    int main()
    {
    	freopen("palsquare.in","r",stdin);
    	freopen("palsquare.out","w",stdout);
    	int B;
    	cin >> B;
    	for(int i = 1; i <= 300; ++i)
    	{
    		int y = i*i; //先进行平方计算，不可将i转成B进制后，再用转成进制后的值平方计算 
    		string B1 = ten_to_r(i,B);
    		//cout << B1 << endl;
    		string B2 = ten_to_r(y,B);
    		if(huiwen(B2))
    		{
    			cout << B1 << " " << B2 << endl;
    		}
    	}
    	return 0;
    }

> 洛谷上写的比较好理解的代码：基本思路分三步。一是i从1到300枚举，将i的平方转换为b进制字符串s；二是判断s是否为回文。三是根据第二步结果，输出i的b进制字符串和i\*i的b进制字符串。

#include<bits/stdc++.h>
    using namespace std;
    bool hw(string s)//判断字符串回文 
    {
        int i,len=s.size();//假设len=4 
        for(i=0;i<len/2;++i)//奇数长度最中间字符不参加比较
        {//偶数长度只比较1-len/2次，次数从0计起就要减1 
            if(s[i]!=s[len-1-i])//s[1]!=s[4-1-1]
                return false;
        }   
        return true;
    }
    string ten2b(int n,int b)//10进制整型n转b进制字符串x 
    {   
        string x,dic="0123456789ABCDEFGHIJKLMNOPQRSTUVWXYZ";
        while(n)
        {
            x=dic[n%b]+x;
            n/=b;
        }
        return x;
    }
    int main()
    {
        int i,m,b;
        string s;
        cin>>b;
        for(i=1;i<=300;++i)
        {
            m=i*i;//生成10进制平方数
            s=ten2b(m,b);
            if(hw(s)) 
                cout<<ten2b(i,b)<<" "<<s<<endl;
        }
        return 0;
    }

[https_www.luogu.com.cn_problem_P1206]: https://www.luogu.com.cn/problem/P1206