[SPOJ] DIVSUM – Divisor Summation

http://www.chenguanghe.com/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 = 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;

    }

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;

        }