Экспоненты в С (п^т)

-3

http://z-trening.com/tasks.php?show_task=5000000069&lang=uk Экспоненты в С (п^т)

#include <stdio.h> 

int main(void) 
{ 
    long long o, s, m, i; 
    long long rez = 1; 

    scanf("%lld %lld %lld", &o, &s, &m); 
    o = o % m; 
    for (i = 0; i < s; i++){ 
     rez = (rez * o) % m; 
    } 
    printf("%lld", rez); 
    return 0; 
}

Она работает на 10 из 20 задач. Есть ли более быстрый способ повысить уровень?

источник

2014-01-30 Bojan Pavlović

C или C++, пожалуйста, сделать свой ум – deW1

Почему вы заботитесь о том, как быстро ваш код работает при условии, что это не правильно? Как это поможет вам быстрее получить неправильный ответ? –

_ «Он работает для 10 из 20 задач» _ Это должно быть первое, что нужно в списке задач. если он работает для задач 20/20, а затем беспокоиться о скорости ... –

Да, есть более быстрый метод: модульное возведение в степень. http://en.wikipedia.org/wiki/Modular_exponentiation

Повторяющееся умножение (ваш алгоритм) выполняется в экспоненциальном времени, а модульное возведение в степень выполняется в полиномиальное время. Вот как это работает:

Допустим, вы хотите, чтобы вычислить А^по модулю М. Во-первых, писать B в двоичной системе:

B = bn,bn-1,...,b1,b0

Это означает, что

B = bn * 2^n + bn-1 * 2^(n-1) + ... + b1 * 2 + b0

Подставляя в выражении A^B:

A^B = A^(2^n)^bn * A^(2^(n-1))^bn-1 * ... * A^2^b1 * A^b0

А^(2^п) могут быть вычислены рекурсивно:

A^(2^n) = (A^(2^(n-1)))^2

Теперь, хитрость заключается в том, чтобы использовать этот идентификатор для вычисления A^(2^я) для каждого я с использованием повторена квадратурой по модулю М. обычных тождеств умножения и возведение в степени удержания для модульной арифметики тоже, так что это является совершенно законным. Полный алгоритм:

input: A,B,M 
output: A^B mod M 

result = 1 
while(B != 0){ 
    if(B is odd){ 
     result = result * A mod M 
    } 
    B = B/2 
    A = A * A mod M 
} 
return result

источник

2014-01-30 09:23:19

Пожалуйста, прочитайте раздел справки: ссылка только ответы не приветствуются (если они не считаются недействительными). Конечно, wiki вряд ли уйдет завтра, но, по крайней мере, вставьте (и кредит!) Суть того, что здесь применяется в вашем ответе –

@EliasVanOotegem ok. –

Простой способ уменьшить количество вычислений использует равенства:

a^(b+c) = a^b*a^c  (1)

(x*y)%z = ((x%z)*(y%z))%z (2)

Этих два равенств может быть использован быстро вычислить (o^1)%m, (o^2)%m , (o^4)%m, (o^8)%m, ...:

o2n = (on * on)%m

Теперь проблема может быть решена с помощью цикла, который выполняет итерацию один раз для каждого бита в s, что означает, что сложность была уменьшена с O(s) до O(log(s).

long long s, o; 
int m; 

// Input s,o,m (code omitted) 

int res = 1, on = o%m; // Assuming int is at least 32 bits 
for (i = 0; i < 35; i++) { // 2^35 is larger than the largest s allowed. 
    if (s & 1 << i) { 
    res = res * on; 
    } 
    on = (on*on)%m; 
} 
printf("%d\n", res);

источник

2014-01-30 10:08:52

Экспоненты в С (п^т)

ответ

Смежные вопросы