Find the value of P and modular inverse of Q modulo 998244353
Given two integer P and Q, the task is to find the value of P and modular inverse of Q modulo 998244353. That is
Note: P and Q are co-prime integers
Examples:
Input: P = 1, Q = 4
Output: 748683265
Explanation:
Refer below for the explanation of the example.Input: P = 1, Q = 16
Output: 935854081
Approach: The key observation in the problem is that Q is co-prime with the 998244353, Then Q-1 always exists which can be computed using Extended euclidean Algorithm
For Example:
For P = 1 and Q = 4
We know that,
That is, 4 * 748683265 = 2994733060 equivalent to 1 mod 998244353
Therefore, 1*4^(-1) = 748683265
Below is the implementation of the above approach:
C++
// C++ implementation to find the // value of P.Q -1 mod 998244353 #include <bits/stdc++.h> using namespace std; // Function to find the value of // P * Q^-1 mod 998244353 long long calculate( long long p, long long q) { long long mod = 998244353, expo; expo = mod - 2; // Loop to find the value // until the expo is not zero while (expo) { // Multiply p with q // if expo is odd if (expo & 1) { p = (p * q) % mod; } q = (q * q) % mod; // Reduce the value of // expo by 2 expo >>= 1; } return p; } // Driver code int main() { int p = 1, q = 4; // Function Call cout << calculate(p, q) << '\n' ; return 0; } |
Java
// Java implementation to find the // value of P.Q -1 mod 998244353 import java.util.*; class GFG{ // Function to find the value of // P * Q^-1 mod 998244353 static long calculate( long p, long q) { long mod = 998244353 , expo; expo = mod - 2 ; // Loop to find the value // until the expo is not zero while (expo != 0 ) { // Multiply p with q // if expo is odd if ((expo & 1 ) == 1 ) { p = (p * q) % mod; } q = (q * q) % mod; // Reduce the value of // expo by 2 expo >>= 1 ; } return p; } // Driver code public static void main(String[] args) { long p = 1 , q = 4 ; // Function call System.out.println(calculate(p, q)); } } // This code is contributed by offbeat |
Python3
# Python3 implementation to find the # value of P.Q -1 mod 998244353 # Function to find the value of # P * Q^-1 mod 998244353 def calculate(p, q): mod = 998244353 expo = 0 expo = mod - 2 # Loop to find the value # until the expo is not zero while (expo): # Multiply p with q # if expo is odd if (expo & 1 ): p = (p * q) % mod q = (q * q) % mod # Reduce the value of # expo by 2 expo >> = 1 return p # Driver code if __name__ = = '__main__' : p = 1 q = 4 # Function call print (calculate(p, q)) # This code is contributed by mohit kumar 29 |
C#
// C# implementation to find the // value of P.Q -1 mod 998244353 using System; class GFG{ // Function to find the value of // P * Q^-1 mod 998244353 static long calculate( long p, long q) { long mod = 998244353, expo; expo = mod - 2; // Loop to find the value // until the expo is not zero while (expo != 0) { // Multiply p with q // if expo is odd if ((expo & 1) == 1) { p = (p * q) % mod; } q = (q * q) % mod; // Reduce the value of // expo by 2 expo >>= 1; } return p; } // Driver code public static void Main( string [] args) { long p = 1, q = 4; // Function call Console.WriteLine(calculate(p, q)); } } // This code is contributed by Ritik Bansal |
Javascript
<script> // Javascript implementation to find the // value of P.Q -1 mod 998244353 // Function to find the value of // P * Q^-1 mod 998244353 function calculate(P, Q) { let mod = 998244353, expo; expo = mod - 2; p = 748683265; // Loop to find the value // until the expo is not zero while (expo != 0) { // Multiply p with q // if expo is odd if ((expo & 1) == 1) { P = (P * Q) % mod; } Q = (Q * Q) % mod; // Reduce the value of // expo by 2 expo >>= 1; } return p; } let p = 1, q = 4; // Function call document.write(calculate(p, q)); // This code is contributed by decode2207. </script> |
Output
748683265
Time Complexity: O(log(expo)), where the expo is calculated in the program
Auxiliary Space: O(1), as no extra space is used