摸索C語言 前身 : 摸索C語言 http://mypaper.pchome.com.tw/iustlovefish 現在即將就讀中興大學資訊科學與工程學系 XD

79愛的鼓勵 1訂閱站台

作法:建表
加速:DP(紀錄關係!! 自己畫表就可以了解了)

/**********************************************************/

#include<stdio.h>
#include<stdlib.h>
#define N 500
int gcd(int a,int b)        
 {        
  int temp;        
  while(a%b)              
   {              
    temp=a;              
    a=b;              
    b=temp%b;                         
   }        
   return b;        
 } 
main()
{
 short int map[501][501]={0};
 int ans[501]={0};
 int a,b,n;
 for(a=1;a<=N;a++)
  for(b=a+1;b<=N;b++)
   {
    map[a][b]=map[a][b-1]+gcd(a,b);
    ans[b]+=map[a][b];
   }
 while(scanf("%d",&n)==1&&n!=0)
    printf("%d\n",ans[n]);
 return 0;
}