题目描述
给定一个十进制自然数的范围和进制的范围,十进制自然数范围在1~44700之间,进制的范围在2~36之间。给定范围里的数中,有些数的平方,在某进制下既是完全平方数又是回文数。本题的任务是统计给定范围内有多少个数的平方满足下列条件:仅在某一进制下既是完全平方数又是回文数。 说明:3^2=9,因为它在十进制和十一进制中都是回文数,所以9不能算;同样,26^2=676也不算。
输入格式
一行四个整数n,m,k,t,分别表示给定的十进制自然数的范围和进制的范围。
输出格式
一行一个正整数,表示给定范围内满足条件的数的个数。
样例数据
input
1 100 9 11
output
12
样例说明
6^2=36=33 base 11
10^2=100=121 base 9
11^2=121=121 base 10
12^2=144=121 base 11
20^2=400=484 base 9
22^2=484=484 base 10
24^2=576=484 base 11
72^2=5184=3993 base 11
82^2=6724=10201 base 9
84^2=7056=5335 base 11
91^2=8281=12321 base 9
100^2=10000=14641 base 9
数据规模与约定
1<=n<=m<=10^5
1<=k<=t<=50;
时间限制:$1 \text{s}$
空间限制:$64 \text{MB}$