Divisor Summation

No problema Divisor Summation , você deve calcular a somatório de todos os os divisores próprios (um divisor estritamente menor que n) de um número n (1 <= n <= 500000). Por exemplo, o somatório dos divisores próprios de 20 é 1 + 2 + 4 + 5 + 10 = 22.

A seguir, o algoritmo trivial para esse problema:

int soma(int n){
 int i;
 int sum=0;
 
 for(i=1;i<n;i++){
  if(n%i==0){
   sum +=i;
  }
 }
 return sum;
} 

Infelizmente ou felizmente, o algoritmo acima excede o tempo limite estabelecido para o problema. Precisamos torná-lo mais rápido. Primeiramente, vamos mostrar que o seguinte resultado é válido:

Teorema 1: Seja d o menor divisor de um número composto n então d ≤  .

Suponha por absurdo que d >  . Logo,

d²  > n

d > n/d

Se d é um divisor de n então existe um k tal que n=k*d, ou seja, k=n/d. Logo, n/d também é divisor de n. Absurdo, encontramos um divisor menor que d.

Com esse resultado, podemos dividir o conjunto dos números divisores de um número em três conjuntos   , e   nos divisores menores que   , maiores que  e divisores  iguais   , respectivamente. Para cada divisor no conjunto podemos encontrar um divisor no conjunto . O conjunto   é igual  se o  número não é um quadrado perfeito ou é unitário se o número é um quadrado perfeito.  Baseado nessa divisão, nós podemos desenvolver o seguinte algoritmo:

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

Para evitar o excesso de multiplicação dentro for podemos retirar a multiplicação calculando o valor do limite antes do início do for da seguinte maneira.

int soma(int n){
    int i;
    int sum = 1;
    double limite = sqrt(n);
    if(n==1) return 0;    
    for(i=2;i<limite;i++){
       if(n%i==0) { 
        sum+=i; sum+=n/i;
       }  
    }
    if(i*i==n)sum += i;
    return sum;
}

Podemos desenvolver uma solução ainda mais eficiente. A idéia básica do algoritmo que vamos desenvolver é a seguinte: vamos pré-calcular a soma dos divisores para todos os números da entrada em uma tabela. Inicialmente, a tabela começa com todas as somas iguais a zerados. Para cada número i, acrescentamos i para todos múltiplos de i a partir do número 2i.

#include <stdio.h>
#include <string.h>
#define MAX 500001
int sum[MAX];
void preprocess(){
 int i,j;
 memset(sum,0,sizeof(sum)); //zerar o vetor sum
 for(i=1;i<MAX;i++){
   for(j=i+i;j<MAX;j=j+i){
   sum[j] +=i;
  }
 } 
}

int soma(int n){
 return sum[n];
}