Calculating number of unharmed leaves
Uses too much memory, and too much time

Your current solution works but uses too much memory.  The problem requirement specifies maximum 16 MB memory to be used.  Your program uses 4 bytes for each number reached including duplicates.  Given the maximum n of 1000000000, maximum caterpillars of 20, and worst case of each caterpillar having value 2, your program would require 40 GB of memory to solve that case.

Also, your program takes too long to run.  Given the worst case scenario mentioned above, your program would need to iterate 10 billion times.  Even at a rate of 1 billion iterations per second, that would take 10 seconds and your time limit is 3.

I will describe some incremental improvements to your solution to fix the memory issue, and then describe a completely different approach that solves the time issue as well.

Slightly better: use sieve approach

Instead of adding reached numbers to a vector and then sorting, you can do better by creating a std::bitset or vector&lt;bool&gt; to store which numbers were reached.  For example, you could create a vector&lt;bool&gt; of size n+1, and then as you reach each number, you set reached[num] = true.  At the end, you scan the vector to count many numbers are unreached.  Assuming that vector&lt;bool&gt; uses 1 bit per element, this solution requires 125 MB of memory, which is still larger than permitted.  However, this at least won't crash your computer if you run it.  Here is a sample solution:

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;

int main (int argc, char const* argv[])
{
    long long n , k;
    std::cin &gt;&gt; n &gt;&gt; k;
    std::vector&lt;int&gt; caterpillars;
    std::vector&lt;long long&gt;v;
    for(int i=0;i&lt;k;i++){
        int a;
        std::cin &gt;&gt; a;
        caterpillars.push_back(a);
    }
    std::vector&lt;bool&gt; reached(n);
    for(int i=0;i&lt;k;i++){
        int val = caterpillars[i];
        for(int j=0;j &lt; n;j+= val) {
            reached[j] = true;
        }
    }
    int unreached = 0;
    for(int j=0;j &lt; n;j++) {
        if (!reached[j])
            unreached++;
    }
    std::cout &lt;&lt; unreached &lt;&lt; std::endl;
    return 0;
}


This program solved the "tough case" 762744433 19 ... in 0.9 seconds on my computer.  However, on the worst case of 1000000000 20 2 2 2 2 ..., it took 16 seconds to solve, which exceeds the time limit of 3 seconds.

Next improvement: use fixed amount of memory

To keep your program within the 16 MB memory limit, you need to do the sieving in segments instead of all at once.  For example, you can compute the solution in segments of 1000000, using only 125 KB of memory for the vector&lt;bool&gt;.  Here is an example of how you can do that:

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;

#define BUFSIZE        1000000

int main (int argc, char const* argv[])
{
    long long n , k;
    std::cin &gt;&gt; n &gt;&gt; k;
    std::vector&lt;int&gt; caterpillars;
    std::vector&lt;long long&gt;v;
    for(int i=0;i&lt;k;i++){
        int a;
        std::cin &gt;&gt; a;
        caterpillars.push_back(a);
    }
    std::vector&lt;bool&gt; reached(BUFSIZE);
    int unreached = 0;
    for(int i=0;i&lt;n;) {
        int size = n-i;
        if (size &gt; BUFSIZE)
            size = BUFSIZE;
        std::fill(reached.begin(), reached.end(), false);
        for (int j=0;j&lt;k;j++) {
            int val = caterpillars[j];
            int first = (i % val);
            if (first != 0)
                first = val - first;
            for (int r = first; r &lt; size; r += val)
                reached[r] = true;
        }
        for (int r = 0; r &lt; size; r++) {
            if (!reached[r])
                unreached++;
        }
        i += size;
    }
    std::cout &lt;&lt; unreached &lt;&lt; std::endl;
    return 0;
}


Similar to the previous program, this program also solved the "tough case" in 0.9 seconds.  It took 14 seconds to solve the worst case, though.  Although there are some optimizations that could be made, it seems that a new algorithm might be needed.

A different approach

This problem is somewhat reminiscent of the FizzBuzz problem.  In FizzBuzz, each number divisible by 3 is Fizz, each number divisible by 5 is Buzz, and each number divisible by both 3 and 5 is FizzBuzz.  If I asked how many numbers between 1 and n are one of Fizz/Buzz/FizzBuzz, you could come up with a \$O(1)\$ solution instead of an \$O(n)\$ solution.

If you think about it a little, n/3 numbers are either Fizz or FizzBuzz, and n/5 numbers are either Buzz or FizzBuzz, and n/15 numbers are FizzBuzz.  So the count of "named" numbers is n/3 + n/5 - n/15.

You can transfer this approach to the caterpillar problem.  Given 2 caterpillars of length a b, the number of leaves eaten is n/a + n/b - n/lcm(a,b), where lcm() is the least common multiple of a and b.

Now you can extend the approach for 3 caterpillars.  With three caterpillars of length a b c, you can have leaves eaten by a, b, c, ab, bc, ac, or abc, where ab means eaten by both a and b.  After doing some reasoning on this, you would come up with the formula:

Leaves eaten = n/a + n/b + n/c - n/lcm(a,b) - n/lcm(b,c) - n/lcm(a,c) + n/lcm(a,b,c)

The formula generalizes to:

Leaves eaten = Sum(n/one) - Sum(n/two) + Sum(n/three) - Sum(n/four) + Sum(n/five) - ...

where Sum(n/five) means the sum of all combinations of the form n/lcm(five caterpillars).

To solve using this method, you need to generate each combination of caterpillars.  With 20 caterpillars, this means you need to go through each of the \$2^{20}\$ combinations, which is actually only 1 million combinations so it should complete quickly.  In general, with \$k\$ caterpillars, this solution solves the problem in \$O(2^k)\$ time.  So you definitely do not want to use this solution with a large number of caterpillars.

I wrote a sample solution that used recursion to generate each combination.  The solve() function tries two cases: including the current caterpillar or not including it, and recurses to the next caterpillar for each case.  You can easily see that this generates 2^k cases.

Here is my solution using this approach:

#include &lt;iostream&gt;
#include &lt;vector&gt;
#include &lt;algorithm&gt;

// Returns greatest common divisor of a and b.
static inline int gcd(int a, int b)
{
    while (b != 0) {
        int tmp = b;
        b = a % b;
        a = tmp;
    }
    return a;
}

// Returns least common multiple of a and b.
static inline long long lcm(int a, int b)
{
    a /= gcd(a, b);
    return (long long) a * b;
}

static int solve(std::vector&lt;int&gt; caterpillars, int curCaterpillar,
        int numUsed, int curLcm, int n)
{
    if (curCaterpillar &gt;= caterpillars.size())
        return 0;

    int val = caterpillars[curCaterpillar];
    int reached = 0;

    // Include current caterpillar:
    long long newLcm = lcm(curLcm, val);
    if (newLcm &lt;= n) {
        if (numUsed &amp; 1)
            reached -= n / newLcm;
        else
            reached += n / newLcm;
        reached += solve(caterpillars, curCaterpillar+1, numUsed+1, newLcm, n);
    }

    // Do not include current caterpillar:
    reached += solve(caterpillars, curCaterpillar+1, numUsed, curLcm, n);

    return reached;
}

int main (int argc, char const* argv[])
{
    long long n , k;
    std::cin &gt;&gt; n &gt;&gt; k;
    std::vector&lt;int&gt; caterpillars;
    std::vector&lt;long long&gt;v;
    int reached = 0;

    for(int i=0;i&lt;k;i++){
        int a;
        std::cin &gt;&gt; a;
        caterpillars.push_back(a);
    }
    n--;
    reached = solve(caterpillars, 0, 0, 1, n);
    std::cout &lt;&lt; n - reached &lt;&lt; std::endl;
    return 0;
}


This solution solved the "tough case" in 0.01 seconds on my computer, and solved the "worst case" in 0.46 seconds.

There are further optimizations that could be made, such as filtering out caterpillars that are multiples of each other before starting the algorithm.  Such caterpillars can be removed without changing the result.  Using that optimization, the worst time I got for any input I tried was 0.08 seconds.