No tags yet

No tag edit access

The problem statement has recently been changed. View the changes.

×
time limit per test: 0.25 sec.

memory limit per test: 65536 KB

memory limit per test: 65536 KB

input: standard

output: standard

output: standard

The following problem is somehow related to the final stage of many famous integer factorization algorithms involved in some cryptoanalytical problems, for example cracking well-known RSA public key system.

The most powerful of such algorithms, so called quadratic sieve descendant algorithms, utilize the fact that if n = pq where p and q are large unknown primes needed to be found out, then if v^{2}=w^{2} (mod n), u ≠ v (mod n) and u ≠ -v (mod n), then gcd(v + w, n) is a factor of n (either p or q).

Not getting further in the details of these algorithms, let us consider our problem. Given m integer numbers b_{1}, b_{2}, ..., b_{m} such that all their prime factors are from the set of first t primes, the task is to find such a subset S of {1, 2, ..., m} that product of b_{i} for i from S is a perfect square i.e. equal to u^{2} for some integer u. Given such S we get one pair for testing (product of S elements stands for v when w is known from other steps of algorithms which are of no interest to us, testing performed is checking whether pair is nontrivial, i.e. u ≠ v (mod n) and u ≠ -v (mod n)). Since we want to factor n with maximum possible probability, we would like to get as many such sets as possible. So the interesting problem could be to calculate the number of all such sets. This is exactly your task.

The most powerful of such algorithms, so called quadratic sieve descendant algorithms, utilize the fact that if n = pq where p and q are large unknown primes needed to be found out, then if v

Not getting further in the details of these algorithms, let us consider our problem. Given m integer numbers b

The first line of the input file contains two integers t and m (1 ≤ t ≤ 100, 1 ≤ m ≤ 100). The second line of the input file contains m integer numbers b

Output the number of non-empty subsets of the given set {b

Input

3 4

9 20 500 3

Output

3

Author: | Andrew Stankevich |

Resource: | Petrozavodsk Winter Trainings 2003 |

Date: | 2003-02-06 |

Codeforces (c) Copyright 2010-2021 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Aug/04/2021 07:23:35 (h2).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|