GUESSPRM- Simple Brute force approach

#1

Well, no need of the Chinese theorem or any other predefined mathematical approach.
the question works well even with an easier brute force approach.

Here is the approach I used for AC in all the test cases:

  1. Throw the maximum number possible in the constraint (100000) (because the square of 10,000 goes to 10000000000) which is maximum possible according to the constraints.
  2. suppose the input of the result is b;
    so (100000*100000 -b) is a factor of the prime P.
  3. compute all the prime factors of the number obtained in step 2.
  4. input all the prime factors into a set and calculate the total number of prime factors of the number.
  5. for i in range of 2 to 10000, find the square for which mod of every element in the set of factors gives a unique number. (the size of the set of all resulting mods will be equal to the set of prime factors of 1000000000000-b).
  6. output the square found in step 5.
  7. calculate the number for which the input satisfies the given condition.
    Here you have your answer with just a simple brute force approach.

The link to the solution:
https://www.codechef.com/viewsolution/25220569

14 Likes
#2

I believe that almost all the people who have passed it do so. Although I am Chinese, I have not used the Chinese Remainder Theorem. The official editorial provides the feasibility proof. Although it is rigorous, it lacks readability. Thank you for your sharing.

12 Likes
#3

if you please share how you come up to this solution ? thanks in advance.

#4

@cap_coder I’ll just put it in simple terms. Suppose I throw the number 10 and get the remainder 2. That simply implies that my prime number devides 100-2=98. Since the number we are finding is prime, we just find all the prime numbers that devide 98. Namely 2,7. Now we know that our answer is one among all the prime factors of 98. Now we simply iterate through a pre computed function that has all the squares of numbers saved in it in increasing order… Like 4,9,16,25,36 and so on… We simply loop through all the squares one by one, and check the value of the square mod all the prime factors of the required number (here 98) . Now 4%2=0, 4%7=4. Here we see we have two different values of mod which is equal to the number of prime factors of 98. So if we output 2, we either get 0 or 4 as input. If the input is 0, our answer is 2, else 7. Similarly for 3,4,5 or more prime factors.

4 Likes
#5

Can you prove mathematically such a number always exists ? The official editorial cannot depend on such assumptions.

7 Likes
#6

I used similar approach,i have the proof:Correct me if i am wrong:
Let’s say a number let’s say A give the same remainder=R on modulo with different prime numbers, There could be at most 17 or 18 i guess as range is [1,10^9]. A=lcm(prime numbers)+R ,Least value of A to give same remainder
Now take the least case of 2,3 which gives same remainder R (R<2 obviously) we will get lcm=6 so any multiple of 6 + R gives us the value for which it occurs same remainder R. so lcm-1 will give unique remainder.Same applies for any quantity of primes, more the quantity more is value of lcm and there will always exist a square number greater than all the primes and less than lcm that gives unique remainder for all.
Now above was for all numbers giving same remainder,how can we prove that among 17(max quantity of primes ) prime maybe two numbers have remainder R1,three numbers have remainder R2 and maybe other also give same remainder.lets say there are N prime numbers.X quantity give same remainder R1, Y quantity give remainder R2,rest all give different remainder.a square number x^2=C * lcm(X prime)+R1=D*lcm(Y prime)+R2,(C,D)>=0, also R1<min prime of set(X prime),so there are very few numbers like this in proportion to 10^9.As there are few we could always find a square that gives unique remainder.

#7

@anand20 since every unique combination of prime numbers on product will produce a discrete number, there must exist a number in this question that has a unique mod with every prime factor in the set.
For example: 2x3=6, 2x5=10, 2×5x3= 30 and so on…
Now take the example 2,5,3
2 devides 2,4,6,8 and so on
3 devides 3,6,9,12 and so on
5 devides 5,10,15 and so on
Now we simply find a number that is decided exactly by one prime factor, or which simply sets a unique mod with every prime factor. The now since the answer is sure to exist, there always must be a unique square existing to make our assumption true. I hope this helps.

#8

@nvdrag123 could you please share your code so that i can see if it helps. ?

#9

https://www.codechef.com/viewsolution/25223276
Here it is.

#11

This is not the proof,you provided.

#12

The method i shared ?

#13

Yes, It is not leading to conclusion of unique numbers, try to read what i have written.

#14

Yes i went through your approach, and though I have a similiar one, you went deep inside considering every possible situation, whereas my assumption is just superficial to yours, just finding a square equal to the lcm-1 and luckily it worked out.

#15

we can get two different mod values from the other squares also right in the example of 2,7 as primes.Then why did u take only 4 as the number.can u please explain?

#16

@vinayreddykall because I am simply iterating from 2 to large numbers. Hence I terminate the loop as soon as it satisfies my requirement.

#17

Thanks a lot for sharing your ideas

#19

Is it possible to prove that there will always be a perfect square which yields different remainders when divided by a given set of prime numbers?

#20

Simply, a complete proof should use the Quadratic Residue theorem.

2 Likes
#22

Obviously such a number exists, but what guarantees you will find such a number in a small range? (like 10000 you’ve used)

1 Like
#23

I tried to implement the above solution but I’m getting a TLE. Can someone pls check my code?
https://www.codechef.com/viewsolution/25319326