8

については、 を計算する必要があり、非常に高速に違いありません! 私の現在のアプローチは次のとおりです。1 <= N <= 10000000002N 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;
        while (n > 63) {
            result = ((result % 1000000007) * (one % 1000000007)) % 1000000007;
            n -= 63;
        }

        for (int i = 1; i <= n; ++i) {
            result = (result * 2) % 1000000007;
        }

    }

    return result;
}

しかし、それは十分に速くないようです。何か案が？

4

5 に答える 5

8

これはより高速になります (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;
}
于 2012-07-02T07:45:19.807 に答える
5

で解決できます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
// (e.g. 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;
}

O(log n)実際にはO(1)、ulong引数の場合 (log n < 63)であることに注意してください。また、このコードはuint、MODULO が素数であるかどうかに関係なく、任意の MODULO (MODULO < 2^32) と互換性があります。

于 2012-07-02T07:44:58.610 に答える
5

このメソッドは、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
于 2014-07-26T02:51:01.823 に答える
1

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 ) ); 
}

これは再帰的なアプローチであり、ほとんどのプログラミング コンテストの時間要件を満たすのに十分な速さです。

于 2013-11-11T06:55:09.023 に答える