# CVCE002 - Editorial

Forgetful Sally - Practice

Author: Muneeb Hussaini
Testers: Srilekhya, Chitturi Sai Suman
Editorialist: Muneeb Hussaini

Easy

None

# PROBLEM

Sally has amnesia and only remembers a few prime numbers (may contain 0 and 1 as well). She wants to know whether a given number x can be represented as a product of only the prime numbers she knows. Output `YES` if x can be represented, `NO` otherwise.

# QUICK EXPLANATION

Given an array of prime numbers and a number x, the array is traversed and x is divided and updated by each number it is divisible by until no such number remains. If the resulting x is 1 then output `YES`, else `NO`.

# EXPLANATION

Given an array a containing n prime numbers [a_0, a_2, a_3, a_{n - 1}] (may include 0 or 1) and an integer x.
The first step is to handle edge cases.

• Edge Case 1: x = 0
If x is 0 then it can be expressed using the given array if and only if the array contains 0. Output `YES` if 0 is found in a and `NO` otherwise.
• Edge Case 2: x = 1
Likewise, if x is 1 then it can be expressed using the given array if and only if the array contains 1. Output `YES` if 1 is found in a and `NO` otherwise.

Once the edge cases are solved, the problem becomes simpler.
x can be represented as a product of the array of prime numbers iff all of the divisors of x are found in the array.
In other words, all of x's prime factors must be present in the array.

One way to solve this is to simply find all the factors of x and store them in a set F. Consider A as set of a. Now, x can be represented using array integers iff F is a subset of A.

The above solution requires iterating over the set \{i\mid\ x\ \%\ i = =0\}, checking if they are prime and then storing them in a set.

A more efficient solution would be to simply divide x by each a_i in a provided x is divisible by a_i.

• The array a is traversed using i.
• If x is divisible by a_i then it is divided by a_i and updated i.e. x = \cfrac{x}{a_i}.
• Above step is repeated as long as x is divisible by a_i.
• Once or if x is not divisible by a_i, i is incremented and the array is further traversed.
Once the above steps take place, the x obtained gives us the output. If x is 1 then all of its prime divisors are present in the array and output is given as `YES`. If x is not 1 then output is given as `NO`.

# SOLUTIONS

Setter's Solution
``````def func():
x, m = map(int, input().split()) #x is number, m is array length
a = [int(x) for x in input().split()] #array with factors
if x == 1 and 1 in a:
return "YES"
if x == 0 and 0 in a:
return "YES"
if x == 0 or x == 1:
return "NO"
while 0 in a:
a.remove(0) #division by zero not possible
while 1 in a:
a.remove(1) #1 is a factor for every number
for i in a:
while(x % i == 0): #x is divided by each factor until it is no longer divisible by it
x //= i
if (x == 1): #if x = 1 then it can be represented as a product of given factors
return "YES"
return "NO"

n = int(input()) #number of test cases
for i in range(n):
print(func())
``````
3 Likes