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));
}
}
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 :)
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
andf2
. Thus, you should multiplysum
byf1+1
and then again byf2+1
. Instead, you multiply byf1+f2+2
, which just makes no sense sincef1+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$$$.
Thank you for you answer . I just have one question . How did you generate Primes upto 10^8? . Did you use normal sieve or segmented sieve?.If possible , could you provide your code ?
I basically used wheel factorization plus segmented sieve. You can find my code on GitHub: https://github.com/Noble-Mushtak/Miscellaneous/blob/master/C%20Programs/gen_primes.c