1
$\begingroup$

Hi All I need some help I am trying to solve this problem which involves computation of sum of divisors and its inverse.

In other words Given an integer $n$ find smallest integer $i$ such that $σ(i)=n$

Explanation about my algorithm. 1 I am finding the sum of Divisor till $10^8$ and the computing its inverse in an hash table and answering each query in $O(1)$ for hast table, But I am getting TLE(Time limit exceeded) The expected running Time is 10s but My code is taking 11s can someone help me with some better approach or some hint how to do this within the given time limit Thanks.

problem link http://www.spoj.com/problems/INVDIV/

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <iostream>
using namespace std;
#define MAX 100000000
#define MAX1 100000000
using namespace std;
unsigned DIV[MAX];
unsigned INVDIV[MAX];
int main()
{

    int tc;unsigned c;
    for (unsigned i=1;i<=10000;i++)
    {
        c=i+1;DIV[i*i]+=i;
        for(int j=i*(i+1);j<MAX1;j+=i) 
        {
            DIV[j]+=i+c;
            c+=1;
        }

    }
    for(unsigned i=2;i<MAX;i++) 
    {
        if (DIV[i]<MAX)
         if (INVDIV[DIV[i]]==0) 
           {
            INVDIV[DIV[i]]=i;
           }
    }
    INVDIV[1]=1;
    int n;
    scanf("%d",&tc);
    while(tc--){
               scanf("%d",&n);
               if(INVDIV[n]!=0)printf("%d\n",INVDIV[n]);
               else printf("-1\n");
    }
    return 0;
}
$\endgroup$
10
  • $\begingroup$ Are you asking for us to tell you why it's timing out, or to help you see a better way to calculate it? $\endgroup$ Commented Jul 21, 2014 at 0:09
  • $\begingroup$ @Semiclassical No I am not asking why It is getting TLE, I am asking for help with some better approach. I posted my code here just to make clear that what I have done till now.Is there a better way to do this? $\endgroup$
    – Lakshman
    Commented Jul 21, 2014 at 0:13
  • $\begingroup$ Are you using that $\sigma$ is multiplicative anywhere in there? If $m,n$ are relatively prime, then $\sigma(mn)=\sigma(m)\sigma(n)$. $\endgroup$ Commented Jul 21, 2014 at 0:16
  • $\begingroup$ @Thomas No, Actually My algorithm is based on sieve method. $\endgroup$
    – Lakshman
    Commented Jul 21, 2014 at 0:21
  • $\begingroup$ Do the spoj people want us discussing their questions here? $\endgroup$ Commented Jul 22, 2014 at 11:15

0

You must log in to answer this question.

Browse other questions tagged .