生活随笔
收集整理的這篇文章主要介紹了
快速pow和sqrt的小技巧 hdu4282
小編覺得挺不錯的,現(xiàn)在分享給大家,幫大家做個參考.
http://acm.hdu.edu.cn/showproblem.php?pid=4282
今年網(wǎng)絡(luò)賽。。天津賽區(qū)。。有道題。。是這樣的。。。X^Z + Y^Z + XYZ = K ?給出K ，求XYZ，我思路很明確。。。枚舉其二，然后二分其一，但是始終TLE。。。。晚上回去之后，看了人家報告，。。。才發(fā)現(xiàn)。。。原來是微軟的函數(shù)pow 惹的禍。。。我本來以為微軟的函數(shù)寫的都很好。。效率很高。。但是我忘了一件事。。就是 pow(int a, int b) 這個函數(shù)可以理解為 pow(double a, double b) ?之所以TLE ?。。是因為微軟提高的兼容性。。而導(dǎo)致時間效率的底下。。（但是令我郁悶的就是。。網(wǎng)上有位仁兄。。也用的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,?ans=0;?? ????????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??
總結(jié)
以上是生活随笔 為你收集整理的快速pow和sqrt的小技巧 hdu4282 的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。
如果覺得生活随笔 網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔 推薦給好友。
