Count Solutions Of ax ≡ b (mod m)
Hard
Computer Mathematics
Modular Arithmetic
46 views
Problem Statement
Count how many x in [0..m-1] satisfy ax ≡ b (mod m).
Input Format
Three integers a b m.
Output Format
One integer count.
Example
4 2 6
2
Constraints
m>0
Input / Output Format
Input Format
Three integers a b m.
Output Format
One integer count.
Constraints
m>0
Examples
Input:
4 2 6
Output:
2
Example Solution (Public)
Let g=gcd(a,m). If b%g!=0 then 0. Else there are g solutions.
Official Solution Code
Let g=gcd(a,m). If b%g!=0 then 0. Else there are g solutions.
Please login to submit solutions.