title: Reducing Integer Fractions Algorithm
body: <p>(This is derived from a recently completed programming competition)</p>
  
  <p>You are given two arrays of 10^5 ints in the range 1..10^7 inclusive:</p>
  
  <pre><code>int N[100000] = { ... }
  int D[100000] = { ... }
  </code></pre>
  
  <p>Imagine the rational number X be the result of multiplying together all the elements of N and dividing by all the elements of D.</p>
  
  <p>Modify the two arrays without changing the value of X (and without assigning any element out of range) such that the product of N and the product of D have no common factor.</p>
  
  <p>A naive solution (I think) would work would be...</p>
  
  <pre><code>for (int i = 0; i &lt; 100000; i++)
      for (int j = 0; j &lt; 100000; j++)
      {
          int k = gcd(N[i], D[j]); // euclids algorithm
  
          N[i] /= k;
          D[j] /= k;
      }
  </code></pre>
  
  <p>...but this is too slow.</p>
  
  <p>What is a solution that takes less than around 10^9 operations?</p>