title: Sum of Greatest Common Divisor (GCD)
body: <p>Calculate</p>
  <p><a href="https://i.stack.imgur.com/G01Jv.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/G01Jv.png" alt="%E2%88%91i%3D1n%E2%88%91j%3D1ngcd%28i%2Cj%29" /></a></p>
  <p>n &lt;= 1000000 (1e6).
  If there is just one test, my code is OK, but if there are 100000 (1e5) test, what should I do to improve my code?</p>
  <p>For example:<br/></p>
  <blockquote>
  <p><strong>Input:</strong><br/>
  60<br/>
  604 84 940 659 989 497 400 656 805 169 305 141 718 691 500 723 658 405 903 859 992 228 614 971 947 621 730 930 416 592 198 351 68 464 347 505 634 364 663 148 385 836 801 515 915 493 836 543 452 931 395 772 461 689 654 625 16 483 819 788</p>
  </blockquote>
  <blockquote>
  <p><strong>Output:</strong><br/>
  664481  8779  1728829  800375  1926541  436636  272512  794360  1237943  41094  150180  27601  964846  888763  442011  979955  799717  279099  1588154  1421789  1944288  79683  687732  1851177  1754783  706093  1002087  1690021  296284  636364  58576  204764  5419  375448  198625  450938  737167  221753  812718  30739  250692  1342475  1225124  469651  1630287  427113  1342475  526336  354587  1694011  263465  1129495  369081  882688  789434  716388  204  409663  1285603  1180671</p>
  </blockquote>
  <p>I had some mistakes (Code edited 1 time)</p>
  <pre><code>#include &lt;cstdio&gt;
  #include &lt;cstring&gt;
  #include &lt;iostream&gt;
  #include &lt;algorithm&gt;
  
  using namespace std;
  
  long long t, n, sum, d[1000010];
  
  int main()
  {
      cin &gt;&gt; t;
      for (int i = 1; i &lt;= t; i++){
          cin &gt;&gt; n;
          sum = 0;
          for (int k = n; k; k--){
              d[k] = (n / k) * (n / k);
              for (int j = k + k; j &lt;= n; j += k)
                  d[k] -= d[j];
              sum += d[k] * k;
          }
          cout &lt;&lt; (sum - n*(n+1)/2)/2 &lt;&lt; '\n';
      }
  }
  </code></pre>
  <p>The contest from here: <a href="http://ntucoder.net/Problem/Details/5610" rel="nofollow noreferrer">http://ntucoder.net/Problem/Details/5610</a></p>