什么是计算2模数的大功率的最快方法
对于1 <= N <= 1000000000 ，我需要计算2 N mod 1000000007 ，它必须非常快！
我目前的做法是：
ull power_of_2_mod(ull n) { ull result = 1; if (n <= 63) { result <<= n; result = result % 1000000007; } else { ull one = 1; one < 63) { result = ((result % 1000000007) * (one % 1000000007)) % 1000000007; n -= 63; } for (int i = 1; i <= n; ++i) { result = (result * 2) % 1000000007; } } return result; }
但它似乎不够快。 任何的想法？
通过平方和二元模幂运算方法检验取幂
这会更快（C中的代码）：
typedef unsigned long long uint64; uint64 PowMod(uint64 x, uint64 e, uint64 mod) { uint64 res; if (e == 0) { res = 1; } else if (e == 1) { res = x; } else { res = PowMod(x, e / 2, mod); res = res * res % mod; if (e % 2) res = res * x % mod; } return res; }
此方法不使用具有O（log（n））复杂度的递归。 看一下这个。
#define ull unsigned long long #define MODULO 1000000007 ull PowMod(ull n) { ull ret = 1; ull a = 2; while (n > 0) { if (n & 1) ret = ret * a % MODULO; a = a * a % MODULO; n >>= 1; } return ret; }
这是来自维基百科的伪（参见从右到左的二进制方法部分）
function modular_pow(base, exponent, modulus) Assert :: (modulus - 1) * (base mod modulus) does not overflow base result := 1 base := base mod modulus while exponent > 0 if (exponent mod 2 == 1): result := (result * base) mod modulus exponent := exponent >> 1 base := (base * base) mod modulus return result
您可以在O(log n)解决它。
例如，对于n = 1234 = 10011010010（在基数2中），我们有n = 2 + 16 + 64 + 128 + 1024，因此2 ^ n = 2 ^ 2 * 2 ^ 16 * 2 ^ 64 * 2 ^ 128 * 2 ^ 1024。
注意2 ^ 1024 =（2 ^ 512）^ 2，因此，如果你知道2 ^ 512，你可以在几个操作中计算2 ^ 1024。
解决方案将是这样的（伪代码）：
const ulong MODULO = 1000000007; ulong mul(ulong a, ulong b) { return (a * b) % MODULO; } ulong add(ulong a, ulong b) { return (a + b) % MODULO; } int[] decompose(ulong number) { //for 1234 it should return [1, 4, 6, 7, 10] } //for x it returns 2^(2^x) mod MODULO // (eg for x = 10 it returns 2^1024 mod MODULO) ulong power_of_power_of_2_mod(int power) { ulong result = 1; for (int i = 0; i < power; i++) { result = mul(result, result); } return result; } //for x it returns 2^x mod MODULO ulong power_of_2_mod(int power) { ulong result = 1; foreach (int metapower in decompose(power)) { result = mul(result, power_of_power_of_2_mod(metapower)); } return result; }
注意，对于ulong参数， O(log n)实际上是O(1) （log n <63）; 并且该代码与任何uint MODULO（MODULO <2 ^ 32）兼容，与MODULO是否为素数无关。
它可以用O（（log n）^ 2）求解。 试试这种方法： –
unsigned long long int fastspcexp(unsigned long long int n) { if(n==0) return 1; if(n%2==0) return (((fastspcexp(n/2))*(fastspcexp(n/2)))%1000000007); else return ( ( ((fastspcexp(n/2)) * (fastspcexp(n/2)) * 2) %1000000007 ) ); }
这是一种递归方法，非常快，足以满足大多数编程竞赛的时间要求。
如果你也想存储那个数组，即。 （2 ^ i）％mod [i = 0 to whatever] than：
long mod = 1000000007; long int pow_mod[ele]; //here 'ele' = maximum power upto which you want to store 2^i pow_mod[0]=1; //2^0 = 1 for(int i=1;i
我希望它对某人有所帮助。