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));
}
}