Рекурсивный и безрекурсный ответ

Question

Извините, что мой родной язык не английский.

Домашнее задание касается расчета модуля. Дивиденд настолько велик (a ^ y, a и y может быть 10 ^ 18), поэтому я должен использовать формулу: (m * n)% d = (m% d * n% d)% d, чтобы закончить это.

Итак, моя логика ниже:

если y = 0, вернуть 1% d

если y = 1, вернуть% d

если y чётно, вернуть рекурсив и пусть m = n = a ^ (y / 2)

если y нечетно, вернуть рекурсивную и пусть m = x ^ (y-1) n = a

проблема в том, что если у нечетно, существует два разных способа решения х:

• 1: рассчитать напрямую (% d)

• 2: использовать рекурсивно и мощность 1

Вы можете увидеть мой код ниже. В ~~ ~~, если заполнить «% d» правильно, а «остаться (1)» неверно.

Но только метод 1 ответ правильный.

При использовании также метода 1 также можно получить правильный ответ. Я все еще хочу знать, почему использование метода 2 неправильно? Итак, как решить проблему с помощью метода 2? Если можно, как мне изменить код? Не могу, почему?

Я пытался напечатать ответ на любом рекурсиве двумя разными способами. Я вижу, что метод 2, хотя у нечетный, его ответ не так, он может вернуть отрицательное значение.

Это мой код ниже:

#include <stdio.h>

long long int a,i,d;

int remain(long long int y){
  if(y==0) return 1%d;
  else if(y==1) return a%d;
  else if(y%2==0) {long long int temp=remain(y/2); return (temp*temp)%d;}
  else if(y%2==1) return ((remain(y-1))*(~~remain(1)~~))%d;
 }

int main(void){
  scanf("%lld %lld %lld",&a,&i,&d);
  printf("%lld\n",remain(i));
  return 0;
} 

, если ввод 16777215 16777215 23842982

Метод 1, ответ 6647725 (правильный).

Метод 2 ответ: 12467225 (неверно).

Т.А. и я не знаю, почему метод 2 неправильный. Мой ТА предлагает мне задать этот вопрос здесь. Большое спасибо.

Answer 1

remain() должно быть определено как long long int.Имея это, вы умножаете два int здесь и наблюдаете целочисленное переполнение:

else if(y%2==1) return ((remain(y-1))*(remain(1)))%d;

Я проверил: как только я установил определение в

long long int remain(long long int y)

Я получил ожидаемый результат

Кстати.Вы могли бы видеть это с включенными предупреждениями компилятора, потому что printf() вызовет предупреждение компилятора (по крайней мере, gcc делает)

Answer 2

Я предполагаю, что вы переполняете тип, который вы используете.Возможно, int64_t remain(int64_t y); будет работать.

Я буду использовать более широкий тип и исправлю стиль вашего кода, чтобы вы увидели, как правильно кодировать.Я также буду использовать целые числа фиксированной ширины, которые вы должны использовать в 99% случаев (если нет веских оснований для этого).

#include <inttypes.h>
#include <stdint.h>
#include <stdio.h>


int64_t a, i, d;


int64_t remain(int64_t y)
{
        int64_t temp;

        if (!y)
                return 1 % d;
        if (y == 1)
                return a % d;
        if (!(y % 2)) {
                temp = remain(y / 2);
                return (temp * temp) % d;
        }
        return (remain(y - 1) * remain(1)) % d;
}


int main(void)
{

        scanf("%"SNCi64" %"SCNi64" %"SCNi64"", &a, &i, &d);
        printf("%"PRIi64"\n", remain(i));

        return 0;
}

Я не исправлял такие вещикак с использованием глобальных переменных, но вы должны.