通过这道题确实体会到A掉数学题确实还是需要经验了,不能猜对哪个地方会丧失精度的话,会一直wa的。其实,这道题我只想出了一半。 题意是 a的p次方 = n,其中n是32位整数,a和p都是整数,求满足条件的最大p。好吧,虽然我是在学数论,但是看到这题,我还是想起了 取对数。那么可以得到,p = ln(n) / ln(a)。既然要求最大的p,那么a最小即可了。那么直接从2开始枚举a不就可以了么。 可是直接枚举a的话肯定会超时的,因为a的范围太大了,比如n的是个大素数,a的范围就是2-n了,一定超时了。然后,我又想出另外一 种方法,对n分解因子,p就是所有因子的指数的最大公约数。呵呵,第二种方法更加会无情的超时,由于int范围很大,实现搞个素数表也不 可能。还是感觉时间不多了,就不多想了,然后搜了下,发现一句话,意识是枚举p。顿时觉得开朗起来,因为p最多是32。由前面可以得到 ln(a) = ln(n) / p。那么只要从32到1枚举p,保证a是整数即可。 后面发现这样精度难于控制,各种原因反正过不了题,看网上的代码,改成计算指数的形式了。因为 a = n的(1/p)次,这个可以用pow函 数算出来,如果a是整数,那么再计算pow(a,p)就会是n了。最难控制的是精度了,还有说n是负数的情况。不知道为什么直接处理负数答案 一直不对,只好把负数变为正数,同时判断p不能是偶数。
代码如下: #include <stdio.h> #include <math.h>
int main() { double fN;//用double就不会溢出了,负数就可以直接转换为正数了 while (scanf("%lf", &fN), fN) { bool bFlag = false; double fP = 31.0; if (fN < 0){fP = 32.0; fN = -fN; bFlag = true;}; while (fP > 0) { //必须加上一个精度,防止往下误差 double fA = pow(fN, 1.0 / fP) + 1e-8; //fA必须转换为int,因为一点点误差,pow之后就会放大很多 double fTemp = pow((int)fA, fP); //必须对负数特殊判断,不可能出现偶数的p if (fabs(fN - fTemp) < 1e-8 && (!bFlag || ((int)fP) % 2)) { printf("%.f\n", fP); break; } fP -= 1.0; } } return 0; }
|