Как я могу рассчитать bigmod (bigmod (a ^ n) -bigmod (b ^ m))?
Я хочу посчитать
(a ^ n% k — b ^ m% k)% k
Но а ^ п а также б ^ м может быть очень большим
Bigmod (bigmod (a ^ n) -bigmod (b ^ m))?
Я пытался рассчитать bigmod (a ^ n) — bigmod (b ^ m) а затем использовал bigmod для результата вычитания тогда я понял, что это дало неправильный ответ!
есть ли рассчитать это?
#include<cstdio>
using namespace std;
template<class T>T big_mod(T n,T p,T m)
{
if(p==0)
return (T)1;
T x=big_mod(n,p/2,m);
x=(x*x)%m;
if(p&1)
x=(x*n)%m;
return x;
}
int main()
{
long long int a=37,b=26,m=10,n=20,mod=1000000008,x,y,z;
x=big_mod(a,m,mod);
y=big_mod(b,n,mod);
z=((x%mod-y%mod)%mod);
cout<<z;
}
Решение
How can i calculate bigmod(bigmod(a^n)-bigmod(b^m)) ?
Пусть ваш модуль будет k, Ваше выражение эквивалентно:
((a^n) % k - (b^m) % k + k) % k
Вам нужно добавить k потому что вычитание может привести к отрицательному результату. Это сделает его положительным, не влияя на результат, так как k % k == 0,
Вычислить (x^y) % k, используйте алгоритм возведения в степень по квадрату и убедитесь, что вы берете модуль по каждому шагу:
x^y % k = ((x^(y / 2))^2) % k if y is even
(x*x^(y - 1)) % k else
Для вашего кода, предполагая, что все остальное работает, вам просто нужно изменить эту строку:
z=((x%mod-y%mod)%mod);
к этому:
z=((x%mod-y%mod+mod)%mod);
Другие решения
Других решений пока нет …