MOMOS - FEASTOFPIGS
The pig's are having a feast tonight!! There are N momos numbered from 0 to N-1. They are all arranged in a row on a table. Also K pigs are attending the feast. The jthpig has hunger a[j]. A pig with hunger a[j] only eats all momos with number i such that when i is divided by a[j], the remainder is 0. For example, if there are 20 momos and a pig has hunger 3, then the pig will eat momos at position 0,3,6,9,12,15,18. Once a momo at a particular position is eaten by one pig, it cannot be eaten by a different pig.
You're task is simple, given the number of momos, and hunger of K pigs, find the total number of momos left after the feast.
The first line of the input contains two integers N and K, where N is the number of momos and K is the number of pigs. Lines 2,3,...,K+1 describe the hunger of K pigs. Line i+1 (1 ≤ i ≤ K) contains a single integer representing the hunger of the ith pig(i.e. a[i]).
It is guaranteed that:
Either (1 ≤ N ≤ 106 and 1 ≤ K ≤ 100) or (1≤ N ≤ 1014 and 1 ≤ K ≤ 20)
The hunger of every pig lies between 1 and N.
A line containing a single integer, which is the number of momos left on the table after all pigs have finished eating.
Input: 20 3 3 6 5 Output: 11
Good idea having 2 kinds of testfiles, however TL is probably unbeatable for slower languages; my PyPy solution needs about 1.55s for a worst-case file.