Возведение в степень

Здравствуйте, имеется задание с такими условиями:
Возведите натуральное число N в целую неотрицательную степень P .

Степень эффективно вычисляется по следующим правилам:

  • Если P = 0, то N P = 1;

  • Если P > 0 и P — чётное, то
    image

  • Если P > 0 и P — нечётное, то
    image

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

Ввод содержит целые числа N и P (1 ≤ N ≤ 1000, 0 ≤ P ≤ 10^18).

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

Выведите одно целое число — остаток от деления N P на 1000000007.

Написал следующий код:

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

int main()
{
	
	long long N = 0;
	int P;
	long long pow2 = 1;
	long long pow3 = 1;
	int x = 0;
	scanf_s("%lld%d", &N, &P);
	if (P == 0) {
		printf("%d", 1);
	}
	else if (P == 1) {
		printf("%lld", N);
	}
	else {
		if (P % 2 == 0) {
			x = pow(N, (P / 2));
			pow2 = pow(x, 2);
			pow2 %= 1000000007;
			printf("%lld\n", pow2);
		}
		else if (P % 2 == 1) {
			x = pow(N, P - 1);
			pow2 = x * N;
			pow2 %= 1000000007;
			printf("%lld\n", pow2);
		}

	}

}

но при тестах выдает ошибку Wrong Answer 13 тест.
Wrong Answer • Решение вывело неверный ответ в указанном тесте.
• Файл не сохранён в среде разработки или на проверку отправлен ошибочный файл.
• Решение содержит неинициализированные переменные.
• Используется значение итерационной переменной после цикла for.

Помогите понять в чем проблема. Заранее спасибо!

а ни чего, что 1000^1018 а у тебя несчастный int? да и long long не помощник в этом случае. Тут длинная арифметика нужна. Или какой-то фокус с хвостом длинного числа при возведении в степень, хотя навряд-ли, остаток от деления на больно хитрое число

ну, вот если заменить int на long long, то он проходит 23 теста и на 23 виснет, либо долго выполняется

значит там входные данные умещаются в long long. сколько там в него по максимому помещается - 20 цифр, а 10^21 уже не уместится. молчу уже про тот максимум с 1021 цифрой ))

Гуглить “возведение в степень по модулю” (например, Алгоритмы быстрого возведения в степень по модулю — Википедия). Грубо говоря, нужно брать остаток от деления на каждом этапе вычисления возведения в степень.

3 лайка

о-о, класс, не зря подозревал что какой-то фокус есть с хвостом при возведении в степень