Numbers
TopCoder SRM 534
Time Limit: 0.3s, Memory Limit: 64MiB
Любимото число на Ели е X. Момичето, също така, има списък с N положителни цели числа A1, A2, …, AN, които намира за "специални". Сега тя се чуди по колко начина може да представи X като произведение на няколко взаимно-прости специални числа.
Вход
На първия ред на стандартния вход ще бъдат зададени целите числа X и N – съответно любимото число на Ели и броя специални числа. На следващия ред ще бъдат зададени N цели числа A1, A2, …, AN – самите специални числа.
Изход
На стандартния изход изведете едно цяло число – броя начини, по които X може да бъде представено като произведение на взаимно-прости специални числа.
Ограничения
- 2 ≤ X ≤ 1018
- 1 ≤ N ≤ 500
- 1 ≤ Ai ≠ Aj 1,000,000,000
Примерен Вход | Примерен Изход |
---|---|
12 5 4 2 5 6 3 | 1 |
42 11 1 2 3 4 5 6 7 13 14 21 42 | 10 |
7420738134810 47 435 625199055 4199 33263 17 222870 284870433 720932379 7 11 31 247110827 23 1771 81809 851968487 13 476379795 1001 5 435274114 38264554 7429 239906525 3 227183706 887045414 606786670 3795 797605175 29 30 747186719 19 2 562347843 74 2294 588002688 7436429 703 591740547 36657492 37 444178205 1002001 217626404 | 110 |
В първия пример има два начина, по които 12 може да бъде представено като произведение на специални числа: като 3 * 4 и като 2 * 6. От тях, обаче, второто представяне не отговаря на изискването на Ели специалните числа, участващи в произведението да са взаимно-прости.
Във втория пример 42 може да бъде представено като 2*3*7, 1*2*3*7, 2*21, 1*2*21, 3*14, 1*3*14, 6*7, 1*6*7, 42, и 1*42.
Във втория пример 42 може да бъде представено като 2*3*7, 1*2*3*7, 2*21, 1*2*21, 3*14, 1*3*14, 6*7, 1*6*7, 42, и 1*42.