1.

/**
* FWP, Ausgewählte Probleme aus dem ACM Programming Contest, WS09
* Problem: 493 - Rational Spiral
* Link: http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&category=6&page=show_problem&problem=434
*
* @author Dennis Wilfert
* @version 1.0, 12/22/2009
*
* Status : Accepted
* Runtime: 0.256
*/
import java.io.BufferedOutputStream;
import java.io.PrintWriter;
import java.util.Scanner;

public class RationalSpiral {

public static void main(String[] args) {

PrintWriter writer = new PrintWriter(new BufferedOutputStream(System.out));

Scanner scan = new Scanner(System.in);

Fraction[] precalc = new Fraction[500800];

// Die ersten 3 Werte eintragen
precalc[0] = new Fraction(1, 1);
precalc[1] = new Fraction(0, 1);
precalc[2] = new Fraction(-1, 1);

// Werte vorberechnen
Fraction tmp;
int pos = 3;
for (int i = 2; i < 642; i++) {
for (int j = 1; j < i; j++) {
tmp = new Fraction((-1) * i, i - j);
if (!tmp.hasDivisor()) {
precalc[pos] = tmp;
pos++;
}
}
for (int j = 1; j < i; j++) {
tmp = new Fraction(i, j);
if (!tmp.hasDivisor()) {
precalc[pos] = tmp;
pos++;
}

}
for (int j = 1; j < i; j++) {
tmp = new Fraction(i - j, i);
if (!tmp.hasDivisor()) {
precalc[pos] = tmp;
pos++;
}

}
for (int j = 1; j < i; j++) {
tmp = new Fraction((-1) * (j), i);
if (!tmp.hasDivisor()) {
precalc[pos] = tmp;
pos++;
}
}
}
// Werte einlesen und den Wert im Array an dieser Position ausgeben
while (scan.hasNext()) {
writer.println(precalc[scan.nextInt()]);

}
writer.flush();
}
}

class Fraction {

private int num;
private int denom;

public Fraction(int num, int denom) {
this.num = num;
this.denom = denom;
}

@Override
public String toString() {
return num + " / " + denom;
}

private int ggT(int a, int b) {
if (b == 0) {
return a;
} else {
return ggT(b, a % b);
}
}
// Zeigt an ob der Bruch einen Teiler !=1 hat

public boolean hasDivisor() {
return Math.abs(ggT(num, denom)) != 1;
}
}