zcmu--1570: Palindromic Numbers

1570: Palindromic Numbers

Time Limit: 1 Sec   Memory Limit: 128 MB

Submit: 102   Solved: 7

[ Submit][ Status][ Web Board]

Description

• • Johnny has figured out that there are some numbers which have an interesting property: they are the same when read from left to right, and from right to left. For example, 5115 and 929 are such numbers, while 31 and 125 are not. Johnny calls such numbers palindromic numbers.

    After a while, Johnny has realized that his definition of palindromic numbers is not really precise. Whether a number is palindromic or not depends on the base in which the number is written. For example, 21 is not palindromic in base 10 but it is palindromic in base 2 (because 21 = 101012).

    Johnny finds it interesting that any number becomes palindromic when it is written in an appropriate base.

    Given a number N, write a program to help Johnny compute the smallest base B such that N is palindromic when written in base B.

Input

• The first line contains t, the number of test cases (about 1000). Then t test cases follow.

  Each test case consists of a number N written in one line (1 <= N <= 1010).

Output

For each given number N, print a line containing the smallest base B such that N is palindromic in base B.

Sample Input

3 1 4 21

Sample Output

2 3 2

題意：給出一個數N，求一個最小的ans使得N在ans進制下是回文數

首先我直接就爆搜了然後發現逾時，然後自己優化，然并卵。。。。還是逾時，後面看了大佬的思路。。。發現大佬果然不一樣...

如果目前數字為N，那麼N可以表示成m*n的形式，也就是N=m*n，那麼我們可以發現，當N為(n-1)進制或者(m-1)進制時，N一定為回文數

證明：首先假設m<n,因為題目要求的是最小的進制數，是以肯定取小的數作為上限答案

1.N=m*n=m*(n-1)+m

2.N%(n-1)=(m*(n-1)+m)%(n-1)=m%(n-1)=m

3.N/(n-1)取整=m

4.m%(n-1)=m

5.是以N在(n-1)進制下答案就是mm一定是回文

是以這樣就可以得出上限是什麼，是以我們隻需要判斷到sqrt(n)的地方，那麼10^10開根号之後也隻有10W次的check，每次check速度基本為常數忽略不計，那麼時間複雜度為O(Tsqrt(n))

另外我們可以發現，當數字較小時，比如4，用這個判斷方法會有問題，但是其實不用想那麼多，既然對于10W次的運算都不會有問題，那麼我們考慮當n<10000時不開sqrt，爆搜答案是什麼即可。

#include<cstdio>
#include<cstring>
#include<cmath>
#include<iostream>
#include<algorithm>
#include<queue>
using namespace std;
int s[500000];
int play(int m,long long x){
    int len=0;
    while(x){
        s[len]=x%m;
        x=x/m;
        len++;
        
    }
    for(int i=0;i<len/2;i++){
        if(s[i]!=s[len-i-1])return 0;
    }
    return 1;
}
int main()
{

    long long n,m,x,y,t;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld",&n);
        int flag=1,len=sqrt(n);
        if(n==1){printf("2\n");continue;}
        if(n<10000)len=n;
        for(int i=2;i<=len+1;i++){
                if(play(i,n)){
                    printf("%d\n",i);
                    flag=0;
                    break;
                }
            }
        if(flag){
            len=sqrt(n);
            for(long long i=len;i>=1;i--){
                if(n%i==0){
                    printf("%lld\n",n/i-1);
                    break;
                }
            }
        }
    }
    return 0;
}