如何编写算法计算所有完全幂的绝对值差？

本文共计1037个文字，预计阅读时间需要5分钟。

%E2%80%9CBingWay%E5%88%9B%E4%BD%9C%E5%93%81%EF%BC%8C%E8%BD%AC%E8%BD%BD%E8%AF%B7%E6%B3%A8%E6%98%8E%E4%BD%9C%E8%80%85%E5%92%8C%E5%87%BA%E5%A4%84%E3%80%82%E5%85%B3%E4%BA%8E%E8%BF%94%E5%9B%9E%E4%B8%8D%E9%87%8D%E5%A4%8D%E6%95%B0%E7%9A%84%E7%AE%97%E6%B3%95%E3%80%8C%E8%B6%A3%E5%91%B3%E7%AE%97%E6%B3%95%E3%80%8D%E5%9B%BD%E5%86%85%E6%9C%89%E5%A5%BD%E5%87%A0%E7%AF%87%E6%96%87%E7%AB%A0%E3%80%82%E8%BF%99%E8%AF%AD%E5%BD%95%E8%AF%BA%E4%BD%BF%E7%BD%91%E7%BB%9C%E7%88%B1%E5%A5%BD%E6%95%B0%E5%AD%97%E7%9A%84%E4%BD%A0%E6%9B%B4%E5%9D%9A%E4%BF%A1%E3%80%82%E2%80%9D

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: 3 8,9 Returns: 1(1是完全幂) 10,15 Returns: -1 1,1000000000000000000 Returns: 1 (最大测试范围) 80000,90000 Returns: 80 测试数据及返回结果有一定的规律，看看哪位能找出运算规律。 我的算法： 算法
staticlongINF=2000000000000000000;
staticlongnearestCouple(longA,longB)
{
longres=INF;
List<long>all=newList<long>();
if(B == A + 1)
{
return res=1;
}
for(intk=2;;++k)
{
longleft=Math.Abs(root(A,k));//返回绝对值
longright=Math.Abs(root(B+1,k))-1;
if(right<2)
break;
if(k==2)
{
if(left<right)
{
res=Math.Min(res,2*left+1);
}
continue;
}
for(longx=left;x<=right;++x)
{
longv=pow(x,k);
if(v<A||v>B)
thrownewException();
all.Add(v);
longu=Math.Abs(root(v,2));
longu2=pow(u,2);
longuu2=pow(Math.Max(1,u-1),2);
longuuu2=pow(u+1,2);
if(u2>A&&u2<B&&u2!=v)
res=Math.Min(res,Math.Abs(u2-v));
if(uu2>A&&uu2<B&&uu2!=v)
res=Math.Min(res,Math.Abs(uu2-v));
if(uuu2>A&&uuu2<B&&uuu2!=v)
res=Math.Min(res,Math.Abs(uuu2-v));
}
}
all.Sort();
for(inti=0;i<all.Count-1;++i)
if(all[i]!=all[i+1])
res=Math.Min(res,Math.Abs(all[i]-all[i+1]));//得到绝对差
returnres==INF?-1:res;//判断是否小于完全幂，小于完全幂返回-1，否则返回res
}
staticlongroot(longn,longp)
{
longz=Math.Max(1,(long)Math.Pow(n,1.0/p)-2);//比较返回较大的数
while(pow(z,p)<n)//z的p次幂是否小于n
{
++z;
}
if(pow(z,p)>n)
{
return-z;
}
else
returnz;

}
staticlongpow(longa,longk)
{
if(k==0)
{
return1;
}
elseif(k%2==0)
{
longz=pow(a,k/2);
returnmul(z,z);
}
else
{
returnmul(a,pow(a,k-1));
}

}
staticlongmul(longa,longb)
{
if(INF/a<b)
returnINF;
else
returna*b;
}