here is the problem link : Anti Hash (SPOJ)

problem is related to polynomial string hashing , you are given P and M and also a string (let's say A) ,find and print another string (say B) which is different than A but have same hash as A.

here is what I am able to think till now : I am treating them as polynomial.

hash(A) = Polynomial Pa hash(B) = Polynomial Pb

since there hash is same hence , (Pa — Pb) % M must be zero.

I am not able to think how to proceed further.

any hint would be helpful , there are no editorial available for this problem.

Thank you.

I am solving this problem but could not understand how to solve it efficiently.

Problem : you are given N numbers (a_i can be up to 10^6 and n can be up to 3*10^5). in one operation you can change a_i to a_i — 1 or a_i + 1 , find minimum operations to make gcd(a_1 , a_2 , . . . , a_n) > 1.

What I am thinking is , from i = 2 to max(a_i) for each number check how many operations are required to make gcd = i and print the minimum cost.

but the complexity of this approach is O(N*max(a_i)) which is resulting in TLE.

if you can only give hint I will try to learn and solve this problem.

thank you for your time.