UVA Solution 493 – Rational Spiral – Solution in C, C++UVA Online Judge Solution 493 – Rational Spiral | Volume 4
UVA Problem Link – 493 – Rational Spiral code
Problem Name: 493 – Rational Spiral solve
Problem Number : UVA – 493 – Rational Spiral solution
Online Judge : UVA Online Judge Solution
Volume: 4
Solution Language : C plus plus
UVA Solution 493 – Rational Spiral Code in CPP:
#include <stdio.h>
#include <stdlib.h>
#include <set>
using namespace std;
set<unsigned long long> S;
int gcd(int x, int y) {
int t;
while(x%y)
t = x, x = y, y = t%y;
return y;
}
int x = 0, y = 1, i, j;
int X[500005], Y[500005];
int idx = 0;
void check() {
if(!x) return;
static int g, tx, ty;
static unsigned long long s;
tx = x, ty = y;
g = gcd(abs(y), abs(x));
tx /= g, ty /= g;
if(tx < 0) ty = -ty, tx = -tx;
X[idx] = tx, Y[idx] = ty;
s = ((unsigned long long)tx)<<32 | (unsigned)ty;
if(S.find(s) == S.end())
idx++, S.insert(s);
}
int main() {
for(i = 2; idx <= 500000; i += 2) {
for(j = 0; j < i && idx <= 500000; j++, x++)
check();
x--, y--;
for(j = 0; j < i && idx <= 500000; j++, y--)
check();
y++, x--;
for(j = 0; j < i && idx <= 500000; j++, x--)
check();
x++, y++;
for(j = 0; j < i && idx <= 500000; j++, y++)
check();
}
int n;
while(scanf("%d", &n) == 1) {
printf("%d / %dn", Y[n], X[n]);
}
return 0;
}
Tags: UVA Online Judge Solution, UVA OJ Solution list, UVA Problems Solution, UVA solver, UVA all problem solution list, UVA 493 – Rational Spiral code in C, UVA UVA Solution 493 – Rational Spiral – Solution in C, C++ code in C++, UVA solution in C, UVA 493 – Rational Spiral solution