読者です 読者をやめる 読者になる 読者になる

UVa11417 GCD

解法
問題文に載っているコードのままでも通るが、同じ計算の無駄を省いて少し高速化する。(0.019秒)

#include <bits/stdc++.h>

using namespace std;

int main() {
  int G[510];

  G[0] = 0;
  for(int i=1; i<501; ++i) {
    G[i] = G[i-1];
    for(int j=1; j<i; ++j)
      G[i] += __gcd(i, j);
  }
  
  for(int N; scanf("%d", &N) && N;) {
    printf("%d\n", G[N]);
  }
  return 0;
}

メモ
for 文で積の和を取る作業に無駄があるのだろうと目星をつけた。よくイメージしたら無駄が確かにあったので省くに至った。