e-olymp 4439. Возведение в степень

04/01/2020 by Владислав Гринькив

Задача

Вычислить значение $a^b$.

Входные данные

Два натуральных числа $a$ и $b$.

Выходные данные

Выведите значение $a^b$, если известно что оно не превосходит $10^{18}$.

Тесты

№	ВХОДНЫЕ ДАННЫЕ	ВЫХОДНЫЕ ДАННЫЕ
1	1 100	1
2	2 10	1024
3	3 7	2187
4	8 9	134217728
5	10 10	10000000000
6	100 9	1000000000000000000

Код

#include <iostream>
using namespace std;

long pow(long a, long b) {
  if(b == 0){
    return 1;
  }
  if(b % 2 == 0){
    return pow(a * a, b / 2);
  }
  return a * pow(a, b - 1);
}

int main() {
  long a, b;
  cin >> a >> b;
  cout << pow(a,b);
  return 0;
}

#include <iostream>

using namespace std;

long pow(long a, long b) {

if(b == 0){

return 1;

}

if(b % 2 == 0){

return pow(a * a, b / 2);

}

return a * pow(a, b - 1);

}

int main() {

long a, b;

cin >> a >> b;

cout << pow(a,b);

return 0;

}

Решение

Для решения задачи создадим функцию «pow()», заметим, что для любого числа $a$ и чётного числа $b$ выполнимо очевидное тождество (следующее из ассоциативности операции умножения):
$$a^b = \left(a^2\right)^{\frac{b}{2}}= \left(a\cdot a\right)^{\frac{b}{2}}$$
Оно и является основным в методе бинарного возведения в степень. Действительно, для чётного $b$ мы показали, как, потратив всего одну операцию умножения, можно свести задачу к вдвое меньшей степени.
Осталось понять, что делать, если степень b нечётна. Здесь мы поступаем очень просто: перейдём к степени b-1, которая будет уже чётной:
$$a^b = a^{b-1} \cdot a$$
Итак, мы фактически нашли рекуррентную формулу: от степени $b$ мы переходим, если она чётна, к $\frac{b}{2}$, а иначе — к $b-1$.

Примечание

Задача требует использование быстрого алгоритма, так как прямое умножение $b$ раз для возведение в $b$-ю слишком медленно, из-за большого количества перемножений. Алгоритм быстрого возведения в степень — это предназначенный для возведения числа в натуральную степень за меньшее число умножений, чем это требуется в определении степени.

Ссылки

Условие задачи на e-olymp
Код на Ideone
Засчитанное решение на e-olymp

Related Images:

e-olymp 2814. Быстрое возведение в степень.

03/07/2018 by Никита Пушкин

Задача

Быстрое возведение в степень

Очень часто возникает задача эффективного вычисления $x^{n}$ по данным $x$ и $n$, где $n$ — положительное целое число.
Предположим, например, что необходимо вычислить $x^{16}$. Можно просто начать с $x$ и 15 раз умножить его на $x$. Но тот же ответ можно получить всего за четыре умножения, если несколько раз возвести в квадрат получающийся результат, последовательно вычисляя $x^{2}$, $x^{4}$, $x^{8}$, $x^{16}$.
Эта же идея, в целом, применима к любому значению $n$ следующим образом. Запишем $n$ в виде числа в двоичной системе счисления (убирая нули слева). Затем заменим каждую «1» парой символов SX, а каждый «0» — символом S и вычеркнем крайнюю слева пару символов SX. Результат представляет собой правило вычисления $x^{n}$, в котором «S» трактуется как операция возведения в квадрат, а «X» — как операция умножения на $x$. Например, $n = 23$ имеет двоичное представление $10111$. Таким образом, мы формируем последовательность SXSSXSXSX, из которой удаляем начальную пару SX для получения окончательного правила SSXSXSX. Это правило гласит, что необходимо «возвести в квадрат, возвести в квадрат, умножить на $x$, возвести в квадрат, умножить на $x$, возвести в квадрат и умножить на $x$», т.е. последовательно вычислить значения $x^{2}$, $x^{4}$, $x^{5}$, $x^{10}$, $x^{11}$, $x^{22}$, $x^{23}$.

Вам нужно для заданного n сформулировать соответствующее правило быстрого возведения числа $x$ в степень $x^{n}$

Входные данные

Одно натуральное число $n$, не превышающее $2 \cdot 10^{9}$.

Выходные данные

Выведите строку для правила возведения числа $x$ в степень $n$ для получения $x^{n}$.

Тесты

#	Входные данные	Выходные данные
1	23	SSXSXSX
2	1
3	16	SSSS
4	1000000	SXSXSXSSXSSSSSXSSSXSSSSSS
5	2018	SXSXSXSXSXSSSSXS

#include <iostream>

using namespace std;

int main() {
    long long n, k = 0;
    cin >> n;
    int c = 0;
    while (n > 1) {
        long long bit = n & 1;
        n >>= 1;
        k <<= 1;
        k |= bit;
        c += 1;
    }
    while (c--) {
        long long bit = k & 1;
        k >>= 1;
        cout << (bit == 0 ? "S" : "SX");
    }
    return 0;
}

#include <iostream>

using namespace std;

int main() {

long long n, k = 0;

cin >> n;

int c = 0;

while (n > 1) {

long long bit = n & 1;

n >>= 1;

k <<= 1;

k |= bit;

c += 1;

}

while (c--) {

long long bit = k & 1;

k >>= 1;

cout << (bit == 0 ? "S" : "SX");

}

return 0;

}

Решение

С помощью первого цикла while в переменную $k$ записываем перевернутый двоичный код числа $n$. Переменную $c$ используем как счётчик кол-ва бит в $n$. Во втором цикле while выводим S или SX если правый бит $0$ или $1$ соответственно, теряя при это последнюю $1$ как и сказано по условию задачи.

Условие задачи можно найти на e-olymp
Код решения — ideone

Related Images:

Ю3.20

01/11/2014 by Марченко Філіп Олександрович

Задача: Для заданных [latex]a[/latex] и [latex]p[/latex] вычислить [latex]x = \sqrt[p]{a}[/latex] по рекуррентному соотношению Ньютона:

[latex]x_{n+1}=\frac{1}{p}*\left[(p-1)x_{n}+\frac{a}{x_{n}^{p-1}}\right][/latex] [latex]x_{0} = a[/latex]

Сколько итераций надо выполнить, чтобы для достижения заданной погрешности [latex]\varepsilon[/latex] выполнялось соотношение:

[latex]\left|x_{n+1}-x_{n}\leq\varepsilon\right|[/latex]?

Тесты:

[latex]a[/latex]	[latex]p[/latex]	Значение корня [latex]x[/latex]	Значение корня [latex]x[/latex], подсчитанного с помощью соотношения	Количество итераций
57	5	2.24479	2.24479	18
16	2	4	4	5
230	2	15.1658	15.1658	7
9	3	2.08008	2.08008	7

Код на С++:

#include <iostream>
#include <stdio.h>
#include <math.h>

using namespace std;
double pow_b (double a, int n){
    if (n==0) return 1;
    double result = 1;
    while (n>0) {
        if (n%2==0) {
            n/=2;
            a*=a;
        }
        else {
            n--;
            result*=a;
        }
    }
    return result;
}
int main () {
    double a, p, eps=0.00001; //инициализируем переменные и задаём погрешность
    cin>>a>>p;
    double x=pow(a, 1/p);  //подсчитываем значение
    double xn=a, x_prev;
    int i=0;
    while (fabs(x-xn) > eps){  //создаём цикл, котоый считает значение с помощью рекурентного соотношения Ньютона
        x_prev=xn;
        xn=(1/p)*(x_prev*(p-1) + a/(pow_b(x_prev, p-1)));
        i++;
    }
    cout<<i<<' '<<xn<<' '<<x; //выводим количество итераций на экран.
    return 0;
}

#include <iostream>

#include <stdio.h>

#include <math.h>

using namespace std;

double pow_b (double a, int n){

if (n==0) return 1;

double result = 1;

while (n>0) {

if (n%2==0) {

n/=2;

a*=a;

}

else {

n--;

result*=a;

}

return result;

}

int main () {

double a, p, eps=0.00001; //инициализируем переменные и задаём погрешность

cin>>a>>p;

double x=pow(a, 1/p); //подсчитываем значение

double xn=a, x_prev;

int i=0;

while (fabs(x-xn) > eps){ //создаём цикл, котоый считает значение с помощью рекурентного соотношения Ньютона

x_prev=xn;

xn=(1/p)*(x_prev*(p-1) + a/(pow_b(x_prev, p-1)));

i++;

}

cout<<i<<' '<<xn<<' '<<x; //выводим количество итераций на экран.

return 0;

}

Код на Java:

import java.util.*;
import java.lang.*;
import java.io.*;


class Ideone {
	public static double bPow (double a, double n){
		if (n==0) return 1;
	    double result = 1;
	    while (n>0) {
	        if (n%2==0) {
	            n/=2;
	            a*=a;
	        }
	        else {
	            n--;
	            result*=a;
	        }
	    }
    	return result;
	}
	public static void main (String[] args)	{
		Scanner sc = new Scanner (System.in);
		int Iterations = 0;
		double eps = sc.nextDouble();
		double a = sc.nextDouble();
		double p = sc.nextDouble();
		double x = a;
		double x_next = (1 / p) * ( (p - 1) * x + a / bPow(x, p - 1)) ;
		while (Math.abs(x_next - x) > eps) {
			x = x_next;
			x_next = (1 / p)*((p - 1) * x + a / (bPow(x, p - 1)) );
			Iterations++;
		}
		System.out.println("Result: " + x_next + "; Iterations: " + Iterations);
	}
}

import java.util.*;

import java.lang.*;

import java.io.*;

class Ideone {

public static double bPow (double a, double n){

if (n==0) return 1;

double result = 1;

while (n>0) {

if (n%2==0) {

n/=2;

a*=a;

}

else {

n--;

result*=a;

}

return result;

}

public static void main (String[] args) {

Scanner sc = new Scanner (System.in);

int Iterations = 0;

double eps = sc.nextDouble();

double a = sc.nextDouble();

double p = sc.nextDouble();

double x = a;

double x_next = (1 / p) * ( (p - 1) * x + a / bPow(x, p - 1)) ;

while (Math.abs(x_next - x) > eps) {

x = x_next;

x_next = (1 / p)*((p - 1) * x + a / (bPow(x, p - 1)) );

Iterations++;

}

System.out.println("Result: " + x_next + "; Iterations: " + Iterations);

}

Решение: Для подсчёта значения корня с помощью рекуррентного соотношения, я создал цикл, в котором организовал подсчёт значения таким образом, что пока разница значения корня x, подсчитанного с помощью функции pow, cо значением текущего корня xn, подсчитанным с помощью соотношения, больше заданной погрешности eps, то, записывая текущее значение в переменную x_prev, подсчитываю новое значение корня. В зависимости от заданной погрешности, программа считает результат и выводит его на экран вместе с кол-вом итераций.

UPD: По предложению Игоря Евгеньевича добавил быстрое возведение в целую степень.

Решение UPD: Чтобы построить алгоритм быстрого возведения в степень, необходимо рассмотреть две ситуации: