[UVa] 264 - Count on Cantor

一開始用數學方法推斷得出，設輸入為n

k為在n的前一斜線列數，故只要找到 (1+k)*k/2 < n 的最大k值，即可判定

k%2 == 1  =>  ((2*n)-(k*k)-k)/2  /  ((k*k)+(3*k)-(2*n)+4)/2
k%2 == 0  =>  ((k*k)+(3*k)-(2*n)+4)/2  /  ((2*n)-(k*k)-k)/2

其實還有更好的方法

令 s 為包含n那一斜列的總項數

偶數列由左下至右上數，故分子為 s-n+1，分母為 k - (s-n)

k % 2 == 1 => s-n+1 / k-s+n
k % 2 == 0 => k-s+n / s-n+1

#include <stdio.h>
#include <stdlib.h>
int main(){
  int k,n;
  while(scanf("%d",&n)!=EOF){
    k=1;
    for(k=1;(k*k+k)/2<n;k++);
    k--;  
    
    
    //printf("k=%d\n",k);
    if(k%2==1)printf("TERM %d IS %d/%d\n",n,((2*n)-(k*k)-k)/2,((k*k)+(3*k)-(2*n)+4)/2);
    if(k%2==0)printf("TERM %d IS %d/%d\n",n,((k*k)+(3*k)-(2*n)+4)/2,((2*n)-(k*k)-k)/2);
  }
  return 0;
}