Расчет больших чисел с модом и Pow
я пытался решить проблему большого мода, используя следующий код.
#include<iostream>
#include<cmath>
using namespace std;
typedef long int li;
li m;
li mod(li b,li p)
{
if(p==0)
return 1;
if(p%2==0)
{
return ((mod(b,p/2)%m)*mod(b,p/2)%m)%m;
//return (li)pow(mod(b,p/2)%m,2)%m;
}
return (b%m*mod(b,p-1)%m)%m;
}
main()
{
li b,p;
while(cin>>b>>p>>m)
{
cout<<mod(b,p)<<endl;
}
}
но он дает различный выход для ((mod (b, p / 2)% m) * mod (b, p / 2)% m)% m и pow (mod (b, p / 2)% m, 2)% Я хочу знать, не являются ли они одинаковыми и почему они дают разные результаты.
образец ввода:
3
18132
17
17
1765
3
2374859
3029382
36123
вывод без функции pow:
13
2
13195
выход с функцией pow:
1
2
31329
тестовый код с функцией pow
#include<iostream>
#include<cmath>
using namespace std;
typedef long int li;
li m;
li mod(li b,li p)
{
if(p==0)
return 1;
if(p%2==0)
{
//return ((mod(b,p/2)%m)*mod(b,p/2)%m)%m;
return (li)pow(mod(b,p/2)%m,2)%m;
}
return (b%m*mod(b,p-1)%m)%m;
}
main()
{
li b,p;
while(cin>>b>>p>>m)
{
cout<<mod(b,p)<<endl;
}
}
Решение
Ответы, о которых вы сообщаете «без функции pow», являются правильными, и ваш код выглядит нормально для меня. Я так думаю ваша проблема в тесте, который вы применяете, не в вашей модульной функции возведения в степень.
pow Функция работает с (двойной точностью) числами с плавающей запятой и не гарантирует точных результатов, даже если оба ее входа — маленькие целые числа. То, что происходит с вами, это то, что в какой-то момент pow возвращает значение, которое чуть меньше целого числа, а затем вы приводите его к long int и получите значение на 1 меньше, чем вы «должны», и после этого все не так.
Например, если вы вычислите 3 ^ 6 mod 17 с вашим кодом, то в один момент он получит 3 ^ 3 mod 17 = 10 (пока все в порядке), затем вычислит pow (10,2) … и, по крайней мере, на моя машина с моим компилятором, получается чуть меньше 100. Таким образом, приведение к li дает 99 вместо 100, а потом мы мертвы.
Я пытался проверить это более подробно, инструментируя ваш код для вывода промежуточных значений, но забавно, что это обычно не получается из-за тонкостей в арифметике с плавающей точкой. (Сохранение промежуточного значения в переменной может привести к дополнительному округлению с плавающей запятой, которое превращает значение чуть меньше целого в точное целое значение.)
Другие решения
Других решений пока нет …