Hatena::Grouptopcoder

tsubosakaの日記

2009-02-25

TCO 09 Qualification Round 1 Medium

| 00:19

1 <= min <= 10^12, min <= max <= min + 10^6のときに自乗数(4,9,16...)で割り切れない数が[min,max]にいくつあるか答えよという問題.

素因数の候補としてはsqrt(min) <= 10^6までの数の自乗した値に関して調べればよい。調べ方としては[min,max]の中で自乗数を素因数としてもつ最小の値から素因数おきにふるっていけばよい。

import java.util.*;

public class SquareFreeNumbers {
  public int getCount(long min, long max) {
    int N =(int)(max - min + 1);
    boolean memo[] = new boolean[N];
    Arrays.fill(memo, true);
    for(long p = 2 ; p * p <= max ; p++){
      long p2 = p * p;
      long s = ((min + p2 - 1)/ p2) * p2;
      for(; s <= max ; s += p2)
        memo[(int)(s - min)] = false;      
    }
    int res = 0;
    for(int i = 0 ; i < memo.length ; i++)
      if(memo[i])res++;    
    return res;
  }
}