c++ - 这段代码的时间复杂度能否进一步降低？

Question

我遇到了编程挑战的几个测试用例超时的问题。任何帮助将不胜感激。

这就是练习:

A palindromic number reads the same both ways. The smallest 6 digit palindrome made from the product of two 3-digit numbers is 101101 = 143 * 707.

Find the largest palindrome made from the product of two 3-digit numbers which is less than N (any input greater than 101101 and less than 1000000).

我的是这样的:

#include<bits/stdc++.h>
using namespace std;
bool check_palindrome(unsigned int a)
{
 
       unsigned int temp = a;
       unsigned int digit ;        //used for reversing
       unsigned int rev_a = 0;    //final reversed number
       int power = 5;             //used for reversing
       unsigned int modulo;       //used for reversing
    while(temp > 0)
    {
        digit = temp / int(pow(10,power));
        temp = temp % int(pow(10 , power));
        rev_a = rev_a + digit * (pow(10 , 5 - power));
        power--;
            
    }
return (a == rev_a) ? true : false ; 
    }

int main()
{
int T;
unsigned int n;

scanf("%d" , &T);
for(int i = 0 ; i < T ; i++)             //for entering number of test cases
    {
    unsigned int max_palindrome=0;
    scanf("%d" , &n);                    //Input the number
    for(int p = 101  ; p <= 999 ; p++)
        {
            int m ;
            int other_number = int(n/p);
            if(other_number > 999 )
                 m = 999;
            else 
                m = other_number;
                
            for( int q = m ; q >100 ; q--)
            {
                if( p*q < 101101)
                       break;
                bool palindrome = check_palindrome(p*q);
                    if(palindrome)
                        {
                            if(p*q > max_palindrome)
                                max_palindrome = p*q;
                                break;
                        }
            }
            
        
        
       }
        printf("%d\n" , max_palindrome);
    }
return 0;
}

Answer 1

与其尝试所有合理的因素对，不如从给定的数字开始倒数。每次遇到一个回文数，看看它是否可以表示为一个合适的乘积(检查从 sqrt(palindrome) 到 101 的所有可能因子)。

优点是一旦找到合适的回文就大功告成，不必继续寻找。

编辑:您甚至不必搜索回文，只需遍历所有可能的前半部分并计算相应的后半部分即可枚举它们。