BingWay原创作品,转载请注明作者和出处。之前写过一篇趣味算法,返回不重复数,引得园子里很多算法高手技痒,我看到的关于返回不重复数的文章有好几篇。这使我更坚信,园子是个很好的技术交流平台。前两天又写了一道算法,原题是英文的,本人英文不是太好,初步翻译了一下,效果自认为还过得去,但怕翻译出来误导了大家,特请坤坤和他那边的英语牛人帮忙翻译,在此,我要特别感谢他们。好了,废话少说,上题目:原:A number is called a perfect power if it can be written in the form m^k, where m and k are positive integers, and k > 1. Given two positive integers A and B, find the two perfect powers between A and B, inclusive, that are closest to each other, and return the absolute difference between them. If less than two perfect powers exist in the interval, return -1 instead.A will be between 1 and 10^18, inclusive.B will be between A+1 and 10^18, inclusive.
译:如果一个数是以m^k这种格式,当m和k都是正整数,而且k大于1,这个数就可以被称为完全幂。给出两个正整数A和B,发现两个完全幂包含在A和B之间,而且这两个数字最接近。并返回一个他们之间的绝对差。如果在区间内存在的完全幂小于两个,就返回-1.A的范围是1至10^18,B的范围是A+1至10^18。
测试数据:1,4 Returns: 38,9 Returns: 1(1是完全幂)10,15 Returns: -11,1000000000000000000 Returns: 1 (最大测试范围)80000,90000 Returns: 80测试数据及返回结果有一定的规律,看看哪位能找出运算规律。我的算法:算法
static long INF = 2000000000000000000;
static long nearestCouple(long A, long B)
{
long res = INF;
List all = new List();
if(B == A + 1)
{
return res=1;
}
for (int k = 2; ; ++k)
{
long left = Math.Abs(root(A, k)); //返回绝对值
long right = Math.Abs(root(B + 1, k)) - 1;
if (right |