TopCoder SRM 394 Level2 1000
http://www.topcoder.com/stat?c=problem_statement&pm=8547&rd=11128
求a到a+b所有的數(shù)的cool divider數(shù)量之和，即本身能被整除但是其n次方不能被整除

由于數(shù)據(jù)高達(dá)10^7，暴力沒有可能，將乘法轉(zhuǎn)化為加法也仍然計算量太大
答案給出了很好的解決方法
對于a到a+b中間的數(shù)，可以整除i的個數(shù)為(a+b)/i - (a-1)/i，以上均為int的除法操作
這樣大大節(jié)省了計算量
唯一要注意的是如果b大于a，會將一部分值本身多計算一次
因此最后要做一點(diǎn)修整

 1import java.util.*;
 2import java.util.regex.*;
 3import java.text.*;
 4import java.math.*;
 5import java.awt.geom.*;
 6
 7public class ProperDivisors
 8{
 9    public int analyzeInterval(int a, int b, int n)
10    {
11        int i,sum = 0;
12        for(i = 2 ; i <= (a+b)/2; ++ i)
13            sum += (a+b)/i - (a-1)/i;
14        for(i = 2 ; i <= (a+b)/2; ++ i){
15            int k = pow(i,n);
16            sum -= (a+b)/k - (a-1)/k;
17        }
18        if(b >= a){
19            sum -= (a+b)/2 - a + 1;
20            if(a == 1) sum++;
21        }
22        
23        return sum;
24    }
25    
26    public int pow(int k, int n){
27        int i;
28        long result = k;
29        for( i = 1 ; i < n; ++ i){
30            result *= k;
31            if(result > Integer.MAX_VALUE)
32                return Integer.MAX_VALUE;
33        }
34        int res = (int)result;
35        return res;
36    }
37}