My code

… was written in C++11 and can be compiled with G++, Clang++, Visual C++. You can download it, too. Or just jump to my GitHub repository.

       
#include <iostream>
       
#include <numeric>
       
 
       
// I optimized the following two routines which originated in my toolbox

       
 
       
// greatest common divisor

       
template <typename T>
       
T gcd(T a, T b)
       
{
       
  // C++17 will have std::gcd(a, b) which is most likely as fast as my implementation
       
 
       
#ifdef __GNUC__
       
  // adopted from https://lemire.me/blog/2013/12/26/fastest-way-to-compute-the-greatest-common-divisor/
       
  // and          https://github.com/lemire/Code-used-on-Daniel-Lemire-s-blog/blob/master/2013/12/26/gcd.cpp
       
  if (a == 0)
       
    return b;
       
  if (b == 0)
       
    return a;
       
 
       
  // MSVC++: _BitScanForward intrinsic instead
       
  auto shift = __builtin_ctz(a | b);
       
  a >>= __builtin_ctz(a);
       
  do
       
  {
       
    b >>= __builtin_ctz(b);
       
    if (a > b)
       
      std::swap(a, b);
       
 
       
    b -= a;
       
  } while (b != 0);
       
  return a << shift;
       
 
       
#else
       
 
       
  // standard GCD
       
  while (a != 0)
       
  {
       
    T c = a;
       
    a = b % a;
       
    b = c;
       
  }
       
  return b;
       
#endif
       
}
       
 
       
// return true if a and b are coprime

       
template <typename T>
       
bool isCoprime(T a, T b)
       
{
       
  // fast reject if both are even (=> gcd(a,b) >= 2)
       
  if (((a|b) & 1) == 0)
       
    return false;
       
 
       
  return gcd(a, b) == 1;
       
}
       
 
       
int main()
       
{
       
  // problem's constants
       
  unsigned int p = 1009;
       
  unsigned int q = 3643;
       
  std::cin >> p >> q;
       
 
       
  // compute phi according to problem statement
       
  auto phi = (p - 1) * (q - 1);
       
 
       
  // lowest number of unconcealed messages, start with highest possible value
       
  unsigned int best = 0xFFFFFFFF;
       
  // sum of all e when best is minimized
       
  unsigned long long sum = 0;
       
 
       
  // iterate over all messages
       
  for (unsigned int encryption = 0; encryption < phi; encryption++)
       
  {
       
    // must be coprime
       
    if (!isCoprime(encryption, phi))
       
      continue;
       
 
       
    auto badP = gcd(p - 1, encryption - 1) + 1;
       
    auto badQ = gcd(q - 1, encryption - 1) + 1;
       
    auto numPlaintext = badP * badQ;
       
 
       
    // same number of unconcealed messages ? add all of them
       
    if (best == numPlaintext)
       
      sum += encryption;
       
    // improved (=lower) number of unconcealed messages ? reset sum
       
    else if (best >  numPlaintext)
       
    {
       
      best = numPlaintext;
       
      sum  = encryption;
       
    }
       
  }
       
 
       
  // display result
       
  std::cout << sum << std::endl;
       
  return 0;
       
}

This solution contains 16 empty lines, 18 comments and 5 preprocessor commands.