Skip to main content

The Thinker's Thesaurus - Mindstormer April 20

Satisfy the condition: x*p^x ≡ q (mod r)

Problem Brief  :

Tanu is a pre final year cs student. She has been given an integer I. And has been asked to compute how many integers x ( 1 <= x <= I) satisfy the below condition:-
x*px ≡ q (mod r)

Prerequisite  :  Basic Mathematics

Approach  :

Brute force solution won't work as 'I' is in range of 10^10 .  So we need to find out some features of that given equation. We have pr-1≡1(mod r) where r is a prime number by Fermat's Little Theorem, it is obvious that pz mod r falls into a loop and the looping section is r−1. Also, z mod r has a looping section r .We can try to list a chart to show what x*px is with some specific i,j. (In the chart shown below, x is equal to i*(r-1) + j.
Proof for the chart shown above: For a certain i,j  we can see that
 x*p^x mod r= ((i*(r−1)+j)mod r)* x ^ (i*(r−1)+j) mod (r−1) =( j−i)*x^j mod r. 
We can also prove that  x*p^x mod r has a looping section r(r−1). So we don't need to list i ≥ r. Therefore, we can enumerate j from 1 to r−1 and calculate q*x^−j . Let's say the result is y, then we have j − i ≡  y (mod r) (You can refer to the chart shown above to see if it is). So for a certain j, the possible i can only be (j−y),r+(j−y),…,r*t + (j−y) . Then we can calculate how many possible answers x in this situation (i.e. decide the minimum and maximum possible t using the given lower bound 1 and upper bound I). Finally we add them together and get the answer.

Setter Code:




Labels

Labels:

Comments

Post a Comment

Popular posts from this blog

Brilliant Mind - Mindstormer April 20 (Product Of All Perfect Square Term Upto A Given No 'n')

Product Of All Perfect Square Term Upto n Question Brief   :           A Number 'n' is given to you , you are said to find the product of all the perfect square term less than or equal to n. Prequisite   :   Basic Mathematics, Preprocessing Approach   :      Perfect Square numbers upto any number n are only these:          (1 2 ,2 2 ,........,(√n) 2 )      In Question it was asked to find the product of all perfect square numbers.i.e. ans =  (1 2  x 2 2   x....... x (√n) 2 ) it can be easily transformed to: ans =  (1   x 2   x....... x √n ) 2 ans= (√n!) 2 So, in each query , for given value of any n, we had to print the square of factorial of square root of n. This can be easily answered in O(1) if we already preprocess the number 1 to sqrt(N) and store their factorial already. SETTER CODE  :
Post a Comment
Read more

Wonder String-1 - Mindstormer April 20

Wonder String Question Breif Given a string containing just the characters 'a', 'b', 'c', 'd', 'e' and 'f', determine if the input string is wonder or not. Pairs are known as (opening element,closing element) : (a,b), (c,d), (e,f) An input string is wonder if: First(opening element) element of pair must be closed by the second(closing element) element of the pair Opening element must be closed by respective closing element in the correct order Note that an empty string is also considered wonder string: Link To Question: https://www.hackerrank.com/contests/mindstormer-apr20/challenges/wonder-string-1 Approach: Hint:  Use Stack If an opening element occurs we push it into stack and when the closing element occurs, we check if the element at the top of stack is corresponding opening element . If its some other element then we return false. Else we pop out  the top most element. If at the end of s...
Post a Comment
Read more

Makarov's Ambition - Mindstormer April 20

 Makarov's Ambition - Mindstormer April 20  Question Brief   :            Two numbers s (number of states) and d (number of districts) followed by a series of 'n' numbers (0 and 1) will be given to you such that s*d=n. All you have to do is check that is there any way to divide the series into n parts such that in majority of states, the guild is victorious. The guild wins if more than half of the districts are won by the guild. Also the division will be consecutive. For example: if s=3, d=2 and series is a1, a2, a3, a4, a5, a6. so division can be made in only these two ways : (a1, a2), (a3, a4), (a5, a6) (a2, a3), (a4, a5), (a6,a1) Prequisite   :   Basic Programming Approach   :         We have to take two arrays, one to store the series and other stores the sum of series till that index. There can be only that number of ways to divide the states as many district...
Post a Comment
Read more