网站开发名词解释,软件公司网站模板图片,zencart网站模板,网页设计与网站建设 倪宝童http://acm.hdu.edu.cn/showproblem.php?pid4282 今年网络赛。。天津赛区。。有道题。。是这样的。。。X^Z Y^Z XYZ K 给出K #xff0c;求XYZ#xff0c;我思路很明确。。。枚举其二#xff0c;然后二分其一#xff0c;但是始终TLE。。。。晚上回去之后#xff0c;看…http://acm.hdu.edu.cn/showproblem.php?pid4282 今年网络赛。。天津赛区。。有道题。。是这样的。。。X^Z Y^Z XYZ K 给出K 求XYZ我思路很明确。。。枚举其二然后二分其一但是始终TLE。。。。晚上回去之后看了人家报告。。。才发现。。。原来是微软的函数pow 惹的祸。。。我本来以为微软的函数写的都很好。。效率很高。。但是我忘了一件事。。就是 pow(int a, int b) 这个函数可以理解为 pow(double a, double b) 之所以TLE 。。是因为微软提高的兼容性。。而导致时间效率的底下。。但是令我郁闷的就是。。网上有位仁兄。。也用的pow。。居然984ms 压线过了这道题。。。汗 ||。。所以我就百度了一下。。找到了快速pow 和sqrt的方法~~ 如下 [cpp] view plaincopy**** ||快速pow多次使用时及其有效 || **** __int64 qpow(int a, int b){ __int64 c, d; c 1; d a; while (b 0){ if (b 1) c * d; b b 1; d d * d; } return c; } **** ||快速1/sqrt(x)牛顿迭代法 || **** float InvSqrt (float x) { float xhalf 0.5f * x; long i *(long*)x; i 0x5f3759df - (i 1); x *(float *)i; x x * (1.5f - xhalf * x * x); return x; } 再列出我最后AC的代码 [cpp] view plaincopy#include stdio.h #include math.h __int64 k; //其实我也试着写了一个pow。。只不过弱爆了。。不够快。。 /* __int64 myqpow(__int64 x, __int64 y) { if (y 1) { return x; } __int64 tmp qpow(x, y/2); if (y%2 1) { return (tmp * tmp * x); } else { return (tmp * tmp); } } */ __int64 qpow(int a, int b) { __int64 c, d; c 1; d a; while (b 0) { if (b 1) c * d; b b 1; d d * d; } return c; } __int64 solve(__int64 x, __int64 z) { __int64 l x 1, r 32768, y (l r) 1;//r k - qpow(x, z) while (l r) { __int64 tmp x * y * z qpow(x, z) qpow(y, z); if (tmp k) { return y ; } else if (tmp k || tmp 0) { r y - 1; } else { l y 1; } y (l r) 1; } /* if (x * y * z qpow(x, z) qpow(y, z) k) { return y ; } */ return 0 ; } int main() { while (scanf(%I64d, k), k) { __int64 i, j, ans0; for (i 2; i 31; i) { for (j 1; ; j) { __int64 tmp1 qpow(j, i); if (tmp1*2 k || tmp1 0) { break ; } // __int64 a solve(j, i); if (solve(j, i)) { ans; // printf(%I64d %I64d %I64d\n, j, a, i); } } } printf(%I64d\n, ans); } return 0; } // 5 6 5 // 3125 7776 150 // 11051 // 40 48 5 // 102400000 254803968 9600 // 357213568
