watchdogs132's blog

By watchdogs132, history, 5 years ago, In English

Link to question :https://www.spoj.com/problems/DIVSUM2/

My approach : -> Find all prime factors of the number below 1 million . Store the frequency of prime factors in a vector while repeatedly dividing the number by the factor , then use the formula to calculate the sum of factors .

->Now if there is a number left ,then that will be either prime or product of two primes. I try to check primality using Miller–Rabin. If number is not prime , then using rho-pollard , I try to generate one of the prime factors , divide to get another and then proceed accordingly.

However, I am getting TLE. I would like to know where I am going wrong . Is it the implementation or the approach ? Thank you.

#include<bits/stdc++.h>

using namespace std;

#define MOD 10000000007

using ll = unsigned long long ;

const ll million=1000000;

vector<ll>v(50000);

ll pow_expo(ll a,ll b)
{

    ll res=1;
    while(b>0)
    {
        if(b&1)
            res=res*a;
        a=a*a;
        b>>=1;
    }
return res;
}


ll pow_exp(ll a,ll b,ll n)
{
    a%=n;
    ll result=1;
    while(b>0)
    {
        if(b&1)
            result=result*a%n;
        a=a*a%n;
        b>>=1;
    }
return result;
}

bool miller_rabin_test(ll d,ll n)
{
    ll a=2+rand()%(n-4);
    ll x=pow_exp(a,d,n);
    if(x==1||x==n-1)
        return true;
    while(d!=n-1)
    {
        x=(x*x)%n;
        d*=2;
        if(x==1)
            return false;
        if(x==(n-1))
            return true;
    }
return false;
}

bool is_prime(ll n,ll k)
{
    if(n<=1||n==4)
    return false;
    if(n==2||n==3)
        return true;
    ll d=(n-1);
    while(d%2==0)
    {
        d/=2;
    }
    for(int i=1;i<=k;i++)
    {
        if(!miller_rabin_test(d,n))
            return false;
    }

return true;
}

ll gcd(ll a,ll b)
{
    if(b==0)
        return a;
    a%=b;
        return gcd(b,a);
}

ll f(ll x)
{
    return ((x*x)+1);
}
ll rho_pollard(ll n)
{
     if(n%2==0)
        return 2;

    ll x=rand(),y=rand(),d=1;

    while(d==1)
    {
        x=(f(x))%n;

        y=(f(f(y)))%n;

        d=gcd(abs(x-y),n);
    }

    return d;
}

ll factorize(ll n)
{
    ll temp=n;
    for(int i=2;i*i<=n;i++)
    {
        if(i>million)
            break;
        while(n%i==0)
        {
            v[i]++;
            n/=i;
        }
    }
    ll sum=1;
        for(ll i=2;i<v.size();i++)
        {
            if(v[i]>0)
                sum*=(pow_expo(i,v[i]+1)-1)/(i-1);
        }

  if(n>1&&is_prime(n,3))
  {
      sum*=(n+1);
       return (sum-temp) ;
  }
  else if(n>1)
  {
            int f1=rho_pollard(n);
            int f2=n/f1;
            sum*=(f1+f2+2);
             return (sum-temp) ;
  }
return (sum-temp) ;

}

int main()
{
    ll q;
    scanf("%I64d",&q);
    while(q--)
    {
        ll n;
        scanf("%I64d",&n);
        fill(v.begin(),v.end(),0);
        printf("%I64d\n",factorize(n));
    }


}

  • Vote: I like it
  • -4
  • Vote: I do not like it

| Write comment?
»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

there is a formula : when you multiply the sum of powers of the prime factor of n (powers from 0 to k while k is the max power of pi) you got the some of the factors . this mean if n = 12 , n = (2)^2 * (3)^1 .
then Sum Of Factors of n = (2^(0) + 2^(1) + 2^(2))*(3^(0) + 3^(1)) = (1+2+4)*(1+3) = 28 this sum includes n ,
so you just need to subtract n from this sum .

hope this help :)

»
5 years ago, # |
  Vote: I like it 0 Vote: I do not like it

The reason you are getting TLE is pretty clear. You are generating the primes up to 1,000,000 for every single test case, which is not necessary. Just initialize the array of primes at the beginning of the program, before you read in any input, and then use the same array throughout all the test cases.

Also, even if you do not get TLE, I would expect you to get WA. When you do Pollard-Rho, you factor $$$n$$$ into two primes f1 and f2. Thus, you should multiply sum by f1+1 and then again by f2+1. Instead, you multiply by f1+f2+2, which just makes no sense since f1+f2+2 does not equal (f1+1)(f2+1).

In my solution to this problem, I did not use Pollard Rho or Miller-Rabin. I just generated all primes under $$$10^8$$$ at the beginning of my program and then did trial division to find the prime factorization. I was able to solve it in 9.32 seconds, which is about half the time limit, so time limit should not be that much of a concern when doing trial division. After all, there are only about $$$6,000,000$$$ primes under $$$10^8$$$.