| Submit | All submissions | Best solutions | Back to list |
HABLU - Hablu and Bablu |
Hablu is a hardworking programmer. He solves lots of easy problems everyday :P. Hablu's teammate Bablu is busy with studies, so amount of solved by him is smaller than Hablu's.
Their coach NannaMia noticed the fact that the number of solved problems by Hablu is a multiple of number of solved problems by Bablu.
Then NannaMia asked Hablu a question. Giving a collection of integers S, NannaMia said that the number of solved problems by Bablu is not a multiple of any integer contained in S (S only contains primes or 1). How many valid integers are there which could be the number of problems solved by Bablu.
As Hablu solves only easy problems, he is unable to solve this one. So, you need to help him :)
Input
The first line contains t, number of test cases (t ≤ 1500).
Each case starts with an integer H, the number of problems solved by Hablu and K, the size of the collection S. The next line contains K space separated integers (the members of S).
Remember that the online judge in which they solve has only(!) 1012 problems. So no number will be greater than 1012. And K will be between 0 and 500.
Output
Print a line for each test case containing the number of possible integers which can be the number of solved problems by Bablu.
Example
Input: 1 58 2 2 3 Output: 2
Note: It may be impossible to pass the time limit in some languages.
| Added by: | Bidhan |
| Date: | 2011-06-26 |
| Time limit: | 1s |
| Source limit: | 25000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | Own Problem , Thanks to Muhammad Ridowan for his alternate solution. |
hide comments
|
||||||
|
2012-07-25 10:09:30 Ravi Kiran
Note: Amount of solved by bablu is *smaller* than Hablu's. Therefore, for cases like 1 3 1 2 Ans = 1 i.e {1} only. Bablu cannot solve 3, although its correct according to remaining constraints. Hope it helps. @problem setter: My O(H^0.5) did pass the judge (with 1.7 secs). Maybe you want to tighten the time limit by a slight factor(~1.5 s), if you're expecting the faster solution itself? :) Last edit: 2011-12-23 18:14:30 |
||||||
|
2012-07-25 10:09:30 BOND
H^(1/2) * K got stuck. |
||||||
|
2012-07-25 10:09:30 [Rampage] Blue.Mary
There's some way to reduce the complexity to O(H^(1/3)+K) per test case :) |
||||||
|
2012-07-25 10:09:30 Problem Solver
Oh man, i thought that O(T*sqrt(X)) would pass, how to avoid prime factorization ? :o ? |
||||||
|
2012-07-25 10:09:30 যোবায়ের
If K = 0, I must say, that online judge is rubbish :p |
||||||
|
2012-07-25 10:09:30 !
The time limit is too strict and test cases are huge :( My O( Slog(S) + sqrt(N)*log(sqrt(N) ) solution timed out. Last edit: 2011-07-02 05:56:11 |
||||||
|
2012-07-25 10:09:30 Muhammad Ridowan
@gaurav yes |
||||||
|
2012-07-25 10:09:30 kanishka
i mean to say every integer in k integer set....is it also 10^12....??? |
||||||
|
2012-07-25 10:09:30 Bidhan
The range is stated clearly in the description. Read carefully. |
||||||
|
2012-07-25 10:09:30 kanishka
i guess 29 and 1..... @bidhan what is the range of k integers....?? |
||||||
RSS