Register
|
Login
Home
News
Competitions
Practice
How to
Rankings
Calendar
Arena
CodeFu 2007
CodeFu'07 Highlights
Jazoon'07 Highlights
Schedule
Rules
Prizes
Results
Competitions
»
Main CodeFu Competitons
»
CodeFu 2007
»
Results
CodeFu 2007 Results
CodeFu Final Round Results
npostolov's solution for 400: Square Count, written in Java
import java.util.LinkedList; import java.util.Queue; public class SquareCount { public int pos(int N) { if (N == 1) { return 1; } long l = 1; long r = 5000000; while (l + 1 < r) { long h = (l + r) / 2; long c = count(h); if (h-c == N){ return (int)h; } if (h - c < N) { l = h + 1; } else { r = h - 1; } } return (int) r; } class P { public int n; public int m; public int l; public P(int n, int m, int l) { this.n = n; this.m = m; this.l = l; } } private long count(long l) { Queue q = new LinkedList(); for (long i = 2; i * i <= l; i++) { q.offer(new P((int) (i * i), 1, (int) i)); } long sum = 0; while (!q.isEmpty()) { P x = ((P) q.poll()); sum += (x.m * l / x.n); for (long i = 2; i * i * (long) x.n <= l; i++) { // System.out.println(i*i*(long)x.n+" "+-x.m); q.offer(new P( (int)(i * i* x.n), -x.m, (int) i)); } } return sum; } private int nzs(long l, long x) { l *= x; int n = (int)nzd(l,x); l/=n; return (int)l; } private long nzd(long a, long b) { if (b==0) return a; else return nzd(b,a%b); } public static void main(String[] args) { SquareCount obj = new SquareCount(); System.out.println(obj.pos(1)); System.out.println(obj.pos(3)); System.out.println(obj.pos(9)); System.out.println(obj.pos(110)); } }