Playing with divisors is fun

#1


Its failing 3 test cases, can you check why?

#2

@duttrohan0302 Take modulo properly, after each and every operation, to prevent overflow, second we cannot divide by 2, as we are taking modulo of number. Take the inverse modulo of 2 in 1000000007, and multiple it with the number instead of dividing it .(p/q)%mod = p * Inv(q) %mod.
If this resolves your doubt mark it as resolved.

1 Like
#3

I am sorry, I didn’t get you. You are talking about perfect squares right?

#4

@duttrohan0302 d=d*(a[i]+1); Here we can have a overflow (suppose all the A[i]==10^9 and their are 100 numbers in array, then no matter what data type you take it will cause overflow in c++). So we must modify this to
d= (d*(a[i]+1)) %mod.
Now the same thing must be done to all other expressions that are multiplying, adding subtracting two numbers.
Now when we are doing operation under some modulo then we cannot do division as that can lead to the wrong answer.
Eg num=16, mod=5,

(num/2)%mod=3
((num%mod)/(2%mod))%mod=0

So we must take inverse of 2 under mod, and modify our operation to

(num*Inv(2))%mod

Where-ever we are dividing.
Here is code for reference.


In this code we are directly using the value on mod inverse of 2.
If you are unfamiliar with inverse modulo, study about it.
If this resolves your doubt mark it as resolved.

#5

I hope I’ve cleared your doubt. I ask you to please rate your experience here
Your feedback is very important. It helps us improve our platform and hence provide you
the learning experience you deserve.

On the off chance, you still have some questions or not find the answers satisfactory, you may reopen
the doubt.