[SPOJ] DIVSUM – Divisor Summation

原题: http://www.spoj.com/problems/DIVSUM/

---

题目大意: 给一个数n,找到它所有的除数的合. 比如number 20 has 5 proper divisors: 1, 2, 4, 5, 10, and the divisor summation is: 1 + 2 + 4 + 5 + 10 = 22.

---

分析: 第一次提交的时候, 老老实实找每个divisor, 结果tle了. 后来想想20/2 = 10, 一次可以把2和10都找到, 所以lgn就可以有.

先上第一次代码:

 public void solve(int testNumber, InputReader in, OutputWriter out) {
            int t = in.readInt();
            for (int i = 0; i < t; i++) {
                int n = in.readInt();
                if (n == 1) {
                    out.printLine(0);
                    continue;
                }
                out.printLine(getSumOfDivisors(n));
            }
        }

        public int getSumOfDivisors(int n) {
            int sum = 0;
            for (int i = 1; i <= n / 2; i++) {
                if (n % i == 0)
                    sum += i;
            }
            return sum;
        }

以上代码tle, 下面是二分代码:

public void solve(int testNumber, InputReader in, OutputWriter out) {
        int t = in.readInt();
        for (int i = 0; i < t; i++) {
            int n = in.readInt();
            if (n==1) {
                out.printLine(0);
                continue;
            }
            out.printLine(getSumOfDivisors(n));
        }
    }
    public int getSumOfDivisors(int n) {
        int sum = 1;
        for (int i = 2; i < n; i++) {
            if (i*i>n)
                break;
            if (n%i==0) {
                sum += i;
                if (i*i!=n)
                    sum+=(n/i);
            }
        }
        return sum;
    }

另外注意的是, 1的结果是….0….