NKOJ 3544 回文数（数学）

发表于 |
字数统计: 437字 | 阅读时长 ≈ 2min

P3544回文数

问题描述

给你一个数N，求出最小的B（B>=2），使得 N在 B进制下为回文数。

输入格式

第一行1个整数TEST，表示数据组数。 接下来TEST行，每行一个整数N。

输出格式

共输出TEST行，每行对应一个答案B

样例输入

3 
1 
4 
21

样例输出

2 
3 
2

提示

30%的数据 TEST<=10，N<=10^4。
100%的数据 TEST<=1,000，N<=10^10。

我们考虑N在B进制下的位数。
如果N在B进制下只有一位，那么B最小为N+1。

如果N在B进制下只有两位，那么设$N=(AA)_B$，那么$N=A\times B+A=A\times(B+1)$，那么B+1必然是N的因数，注意$A<B​$，分解因数讨论即可。

如果N在B进制下至少有三位，那么B进制下最小的三位数为$(100)_B$，那么$N>=B^2$，那么有$B<=\sqrt{N}$，那么枚举即可。

最后将三种情况取最小的B即可。复杂度$T\sqrt{N}$

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
#include<cstdio>
#include<iostream>
#include<algorithm>
#define ll long long
using namespace std;
ll T,n,tot,A[123];
bool ok(ll x,ll k)
{
	tot=0;
	while(x)
	{
		A[++tot]=x%k;
		x/=k;
	}
	ll i=1,j=tot;
	while(i<=j)
	{
		if(A[i]!=A[j])return 0;
		i++;j--;
	}
	return 1;
}
void Solve(ll x)
{
	ll i,t1=x+1;
	for(i=2;i*i<=x;i++)
	{
		if(x%i==0)continue;
		if(ok(x,i))break;
	}
	if(i*i<=x){printf("%lld\n",i);return;}
	for(i=1;i*i<=x;i++)
	if(x%i==0)
	{
		if(x/i-1>1)t1=min(x/i-1,t1);
	}
	printf("%lld\n",t1);
}
int main()
{
	scanf("%lld",&T);
	while(T--)
	{
		scanf("%lld",&n);
		Solve(n);
	}
}