読者です 読者をやめる 読者になる 読者になる

TopCoder SRM 672 Div1 Easy: Procrastination

競技プログラミング SRM

解法

n-200からn+200までの数の約数を全列挙して殴る。

コード

import java.util.Arrays;
import java.util.HashSet;

public class Procrastination {

    public long findFinalAssignee(long n) {
	HashSet<Long> divisers = new HashSet<>();
	long min = Math.max(2, n - 200);
	long max = n + 200;
	int sqrt = (int) Math.sqrt(max);
	for (int i = 2; i <= sqrt; i++) {
	    for (long num = min; num <= max; num++) {
		if (num < i) {
		    continue;
		}
		if (num % i == 0) {
		    divisers.add((long) i);
		    if (num / i >= 2) {
			divisers.add(num / i);
		    }
		}
	    }
	}
	Long[] d = divisers.toArray(new Long[divisers.size()]);
	Arrays.sort(d);
	for (long p : d) {
	    if (n - 1 <= p) {
		break;
	    }
	    if (n > p && n % p == 0) {
		n++;
	    } else if ((n - 1) > p && (n - 1) % p == 0) {
		n--;
	    }
	}

	return n;
    }

}