DCP-527: Modular Inverse Back to All Problems

Easy Math > Number Theory


Modular inverse of a number **a** (mod **m**) is **b** such that `` a*b=1 (mod m) `` where **0 &le; a,b &lt; m** we write **a <sup>-1</sup>=b (mod m)** or **b <sup>-1</sup>=a (mod m)** which means **a** and **b** are modular inverse of each other in mod **m**. Note that , modular inverse of a number is not always exist. In particular modular inverse of a number **a** (mod **m**) exist if and only if ```gcd(a,m)=1``` . Here gcd means greatest common divisor. In this problem you have to find modular inverse of **2** modulo **m**. In other word given **m** , ( 2 < m <2<sup>64</sup> ), find a number **a** such that ``` (2*a)=1 mod(m) ``` or report it does not exist. Input: ------ Input starts with an positive integer **T &le; 10<sup>5</sup>** , denoting the number of test cases. Each case contains an integer **m** ( 2 < m <2<sup>64</sup> ) in a line Output: ------- For each test case print a integer **a** **(0 &le; a &lt; m)**, such that a is modular inverse of 2 (mod **m**), if no such **a** exist print **-1**. Sample Input ------------ 2 3 4 Sample Output ------------- 2 -1


Problem Setter:

Md. Tariqul Islam

Please login to submit solution to this problem.

Problem Limits

Language Time Limit (seconds)
C 0.50
C++ 0.50
C++14 0.50
C# 1.00
Go 1.00
Java 1.00
JavaScript 1.00
Objective-C 1.00
Perl 1.00
PHP 1.00
Python 1.00
Python3 1.00
Ruby 1.00
VB.Net 1.00

Problem Stats

57/336

Solve/Submission

Ranking

# User Language Timing
01 mhiceiuk Cpp 0.03s
02 tariqiitju Cpp 0.03s
03 pulak_ict_mbstu Cpp 0.03s
04 shamiul93 Cpp 0.03s
05 ehsan_sshuvo96 Cpp 0.03s
06 mash02 Cpp 0.04s
07 kabbya Cpp 0.04s
08 Tahseen Cpp 0.04s
09 dot0 Cpp 0.04s
10 Ramprosad Cpp 0.04s
11 feodorv C 0.04s
12 leenaiitju Cpp 0.04s
13 Not_Found0001 Cpp 0.04s
14 Rajan_sust Cpp 0.04s
15 shamimjucse Cpp 0.04s
16 shishir09 Cpp14 0.04s
17 rayhan50001 Cpp14 0.04s
18 L1nK1n Cpp 0.04s
19 S_Saqib Cpp 0.07s
20 kakarotto Cpp 0.08s
21 prateepm Cpp14 0.13s
22 Bisnu039 Cpp 0.13s
23 deloar1 Cpp 0.13s
24 rabbycse Cpp 0.18s
25 nasib_mbstu Cpp 0.18s
26 unknown420 Cpp 0.18s
27 Log_out Cpp 0.18s
28 joty_ict Cpp 0.18s
29 hmsayem Cpp 0.18s
30 bhaktadip Cpp14 0.18s
31 fayedanik Cpp 0.18s
32 Riad_IIT7 Cpp14 0.18s
33 Silent_Warrior Cpp 0.18s
34 subhashis_cse Cpp 0.18s
35 t0whid Cpp 0.18s
36 prodipdatta7 Cpp14 0.18s
37 Shakil_Mahmud Cpp 0.19s
38 AlaminJust Cpp 0.19s
39 st3inum Cpp 0.35s
40 Riaz_BSMRSTU Cpp 0.36s
41 obujgalib Cpp 0.37s
42 we7d Python3 0.49s
43 sabertooth Python3 0.57s
Feedback

Your feedback is our precious!



Or call +88 02 9853138 for support