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就可以有.
原题: 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;
}
