Учитывая сумму GP (1 - ((n-1) / n) ^ r) = P / Q, как рассчитать эту долю P / Q, когда r велико, и вывести (P * Q ^ (- 1))% 1000000007 где Q ^ (- 1) является модульной инверсией Q по модулю 1000000007
Я могу вычислить (n-1) ^ r и n ^ r, используя модульное возведение в степень, а затем вывести P * Q ^ (- 1) с использованием модульной обратной формулы с использованием маленькой теоремы Ферма, но это не правильно, потому что я думаю, что (n ^ r) модульное обратное не то же самое, что Q ^ (- 1), и если я вычисляю Q без использования модульного возведения в степень, он переполняется даже долгов C ++.Так что, пожалуйста, подскажите, что я делаю не так?
ll modInverse(ll a, ll m)
{
ll ans = power(a, m-2, m); //for finding modular inverse
return ans;
}
ll power(ll x, ll y, ll p)
{
ll res = 1;
x = x % p;
while (y > 0) // ll is long long
{ //p=1000000007;
if (y & 1) //for calculating n^r and (n-1)^r
res = (res*x) % p;
y = y>>1;
x = (x*x) % p;
}
return res;
}
вычисление P * Q ^ (- 1)% 1000000007 дает неожиданный ответ для больших значений из-за переполнения, и если переполнение ограничено с помощью мода 1000000007, давая неверныйценности.Я использую небольшую теорему Ферма для вычисления модульного метода обратной и быстрой степени для оценки n ^ r.
для