# 如何避免模数乘法溢出？

## 本文概述

``````// A Simple solution that causes overflow when
// value of (a % mod) * (b % mod) becomes more than
// maximum value of long long int
#define ll long long

ll multiply(ll a, ll b, ll mod)
{
return ((a % mod) * (b % mod)) % mod;
}``````

log n求幂算法

)。

``````// To compute (a * b) % mod
multiply(a, b, mod)
1)  ll res = 0; // Initialize result
2)  a = a % mod.
3)  While (b > 0)
a) If b is odd, then add 'a' to result.
res = (res + a) % mod
b) Multiply 'a' with 2
a = (a * 2) % mod
c) Divide 'b' by 2
b = b/2
4)  Return res``````

## C ++

``````// C++ program for modular multiplication without
// any overflow
#include<iostream>
using namespace std;

typedef long long int ll;

// To compute (a * b) % mod
ll mulmod(ll a, ll b, ll mod)
{
ll res = 0; // Initialize result
a = a % mod;
while (b > 0)
{
// If b is odd, add 'a' to result
if (b % 2 == 1)
res = (res + a) % mod;

// Multiply 'a' with 2
a = (a * 2) % mod;

// Divide b by 2
b /= 2;
}

// Return result
return res % mod;
}

// Driver program
int main()
{
ll a = 9223372036854775807, b = 9223372036854775807;
cout << mulmod(a, b, 100000000000);
return 0;
}``````

## Java

``````// Java program for modular multiplication
// without any overflow

class GFG
{

// To compute (a * b) % mod
static long mulmod( long a, long b, long mod)
{
long res = 0 ; // Initialize result
a = a % mod;
while (b > 0 )
{
// If b is odd, add 'a' to result
if (b % 2 == 1 )
{
res = (res + a) % mod;
}

// Multiply 'a' with 2
a = (a * 2 ) % mod;

// Divide b by 2
b /= 2 ;
}

// Return result
return res % mod;
}

// Driver code
public static void main(String[] args)
{

long a = 9223372036854775807L, b = 9223372036854775807L;
System.out.println(mulmod(a, b, 100000000000L));
}
}

// This code is contributed by Rajput-JI``````

## Python3

``````# Python3 program for modular multiplication
# without any overflow

# To compute (a * b) % mod
def mulmod(a, b, mod):

res = 0 ; # Initialize result
a = a % mod;
while (b > 0 ):

# If b is odd, add 'a' to result
if (b % 2 = = 1 ):
res = (res + a) % mod;

# Multiply 'a' with 2
a = (a * 2 ) % mod;

# Divide b by 2
b / / = 2 ;

# Return result
return res % mod;

# Driver Code
a = 9223372036854775807 ;
b = 9223372036854775807 ;
print (mulmod(a, b, 100000000000 ));

# This code is contributed by mits``````

## C#

``````// C# program for modular multiplication
// without any overflow
using System;

class GFG
{

// To compute (a * b) % mod
static long mulmod( long a, long b, long mod)
{
long res = 0; // Initialize result
a = a % mod;
while (b > 0)
{
// If b is odd, add 'a' to result
if (b % 2 == 1)
{
res = (res + a) % mod;
}

// Multiply 'a' with 2
a = (a * 2) % mod;

// Divide b by 2
b /= 2;
}

// Return result
return res % mod;
}

// Driver code
public static void Main(String[] args)
{
long a = 9223372036854775807L, b = 9223372036854775807L;
Console.WriteLine(mulmod(a, b, 100000000000L));
}
}

// This code is contributed by 29AjayKumar``````

``84232501249``

• 回顶