package no002; import java.util.ArrayList; import java.util.Arrays; import java.util.HashSet; import java.util.PriorityQueue; import java.util.Scanner; public class Main { public static void main(String[] args) { ArrayList primeList = Sieve.primeList(10000); int[] grundy = new int[10001]; Arrays.fill(grundy, -1); grundy[0] = grundy[1] = 0; for(int i=2;i<=10000;i++) { ArrayList factor = Sieve.primeFactor(primeList, i); HashSet hs = new HashSet<>(); for(Sieve.Factor f:factor) { hs.add(grundy[i/f.base]); if (f.exp >= 2) { hs.add(grundy[i/f.base/f.base]); } } PriorityQueue pq = new PriorityQueue<>(hs); for(int j=0;j<=10000;j++) { if (pq.isEmpty() || pq.poll() != j) { grundy[i] = j; break; } } } Scanner sc = new Scanner(System.in); int n = sc.nextInt(); int ans = 0; for(int i=0;i primeList(int max) { boolean[] isPrime = isPrimeArray(max); ArrayList primeList = new ArrayList<>(); for(int i=2;i<=max;i++) { if (isPrime[i]) { primeList.add(i); } } return primeList; } public static ArrayList primeFactor(ArrayList primeList,long num) { ArrayList ret = new ArrayList(); for(int p:primeList) { int exp = 0; while(num % p == 0) { num /= p; exp++; } if (exp > 0) { ret.add(new Factor(p,exp)); } } if (num >= 2) { ret.add(new Factor((int) num,1)); } return ret; } public static ArrayList primeFactor(long num) { return primeFactor(primeList((int) (Math.sqrt(num) + 0.5)), num); } public static class Factor { int base,exp; public Factor(int base,int exp) { this.base = base; this.exp = exp; } public String toString() { return base + "^" + exp; } } }