So, I am doing a Question which I am able to reduce to the following problem :-

EQ1:- C2 = (a2^2)%P

EQ2:- C2+C1 = ((a1+a2)^2)%P

find any one pair (a1,a2) satisfying above equations where P is prime number >=3 and C1 and C2 are integer between >=0 and <P.

constraints:-

1) P < 1e9+9

2) TestCases(T) <= 1e4

3) TimeLimit 4s

My approached (basically trying to find sqareroot modulus)

1) bruteforces over each value from 0 to P/2 and store squareroot modulus but that's O(T*P)

2) Tonelli–Shanks algorithm but that also is getting TLE

How to solve above equation efficiency?

Suppose I have a weighted graph with equal positive weight (let it be K) on each edge. Now I want to count the number of ways to assign weights to vertices SUCH THAT if there is an edge between X and Y then max(W[X], W[Y])=K where W[X] means assigned weight to vertex X.

can someone solve it in better than O(2^n). means for n<=40

Suppose I have a weighted graph with equal positive weight (let it be K) on each edge. Now I want to count the number of ways to assign weights to vertices SUCH THAT if there is an edge between X and Y then max(W[X], W[Y])=K where W[X] means assigned weight to vertex X.

can someone solve it in better than O(2^n).

Anyone could help me with LCM constrainsts. Please DM

Thanks