Thursday, November 3, 2016

Count number of solutions of x^2 = 1 (mod p) in given range - GeeksforGeeks

Count number of solutions of x^2 = 1 (mod p) in given range - GeeksforGeeks
Given two integers n and p, find the number of integral solutions to x2 = 1 (mod p) in the closed interval [1, n].

One simple solution is to go through all numbers from 1 to n. For every number, check if it satisfies the equation. We can avoid going through the whole range. The idea is based on the fact that if a number x satisfies the equation, then all numbers of the form x + i*p also satisfy the equation. We traverse for all numbers from 1 to p and for every number x that satisfies the equation, we find the count of numbers of the form x + i*p. To find the count, we first find the largest number for given x and then add (largest-number – x)/p to the result.
`int` `findCountOfSolutions(``int` `n, ``int` `p)`
`{`
`    ``// Initialize result`
`    ``ll ans = 0;`

`    ``// Traverse all numbers smaller than`
`    ``// given number p. Note that we don't`
`    ``// traverse from 1 to n, but 1 to p`
`    ``for` `(ll x=1; x<p; x++)`
`    ``{`
`        ``// If x is a solution, then count all`
`        ``// numbers of the form x + i*p such`
`        ``// that x + i*p is in range [1,n]`
`        ``if` `((x*x)%p == 1)`
`        ``{`
`            ``// The largest number in the`
`            ``// form of x + p*i in range`
`            ``// [1, n]`
`            ``ll last = x + p * (n/p);`
`            ``if` `(last > n)`
`                ``last -= p;`

`            ``// Add count of numbers of of the form `
`            ``// x + p*i. 1 is added for x itself.`
`            ``ans += ((last-x)/p + 1);`
`        ``}`
`    ``}`
`    ``return` `ans;`
`}`

Read full article from Count number of solutions of x^2 = 1 (mod p) in given range - GeeksforGeeks