MOD 1000000007 好像不对

Question

我有一个简单的问题，如何让这个函数 return mod 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

模组中的

"division" 与普通除法有很大不同，所以你不能只在 C/C++ 中使用 / 和 %；您需要一种算法来找到乘法逆元。参见 https://cs.stackexchange.com/questions/10552/division-modulo-a-prime-in-modular-arithmetic

MOD 1000000007 seems to be incorrect