MOD 1000000007 кажется неверным

Question

У меня простой вопрос, как сделать так, чтобы эта функция возвращала значение мода 1000000007? Я пытаюсь достичь ((k+n)*n/k+n)%MOD, избегая при этом промежуточного переполнения.

long long func(long long n,int k){
    return ((k+n)*n)/k+n;
}

В соответствии с этими 3 формулами: (a+b)%c=((a%c)+(b%c))%c и (a-b)%c=((a%c)-(b%c))%c и (a*b)%c=((a%c)*(b%c))%c я написал следующее:

long long func(long long n,int k){
    return (((((((k%MOD)+(n%MOD))%MOD)*(n%MOD)))/k)%MOD+(n%MOD));
}

Что кажется неправильным.

Answer 1

«деление» в группе по модулю сильно отличается от обычного деления, поэтому вы не можете просто использовать / и % в C / C ++;вам нужен алгоритм, чтобы найти мультипликативный обратный. Смотри https://cs.stackexchange.com/questions/10552/division-modulo-a-prime-in-modular-arithmetic