Division

Source: Codeforces 1444A

1. Read the problem and summarise the task requirements.
   • Try to keep your response to a couple of sentences.
2. We want the biggest divisor of p_i that satisfies some other condition.
   • When is x_i = p_i?
   • Provide a simple characterisation of the cases that are left to solve.

In this problem, we are concerned with the multiplicative structure of integers.

3. What framework is typically useful for analysing multiplication and division?

4. Rewrite the problem in terms of this framework.
   • Make use of your answer to Question 2.
   • Does it matter that p can be much larger than q?
5. Design an algorithm to solve the problem.
   • Analyse each component of the above framework independently, as much as possible.

6. Analyse the time complexity of your algorithm and estimate its running time.

7. Implement this algorithm in code.
   • Reflector:
     • What potential pitfalls can you think of?
     • Write some tests to check for these pitfalls.
   • Other group members:
     • Write a program which solves the problem.
   • Run your tests and debug if necessary.
8. Submit your program for judging!
   • Debug as required.