SPOJ FACT1 Prime factorization up to 10^20

help
1

I have implemented the brent’s algorithm.
But still i am getting TLE.
Please help:

#include <bits/stdc++.h>
#define ll long long
#define endl "\n"
using namespace std;

ll mul(ll a, ll b, ll mod)
{
	ll res=0;
	while(b)
	{
		if(b&1)
			res=(res%mod+a%mod)%mod;
		a=(a%mod + a%mod)%mod;
		b>>=1;
	}
	return res;
}

ll f(ll x, ll c, ll n)
{
	return (mul(x,x,n)+c)%n;
}

ll binpower(ll a, ll b, ll p)
{
	ll res=1;
	while(b)
	{
		if(b&1)
			res = mul(res,a,p);
		a = mul(a,a,p);
		b>>=1;
	}
	return res;
}

bool fermant(ll n, ll k)
{
	if(n<=1||n==4)
		return 0;
	if(n<=3)
		return 1;
	if(n%2==0)
		return 0;
	vector<ll> primes={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73,79,83,89,97};
	for(auto i:primes)
		if(i==n)
			return 1;
	
	for(ll i=1;i<=k;++i)
	{
		ll a=2+rand()%(n-4);
		if(__gcd(a,n)!=1)
			return 0;
		if(binpower(a,n-1,n)!=1)
			return 0;
	}
	return 1;
}

ll brent(ll n)
{
	ll g=1;
	ll x,y,xs,q=1;
	srand(time(NULL));
	x=(rand()%(n-2))+2;
	ll c=(rand()%(n-1))+1;
	int l=1;
	int m=128;//Num of times multiplied
	while(g==1)
	{
		y=x;
		for(int i=1;i<l;++i)
			x=f(x,c,n);
		int k=0;
		while(k<l&&g==1)
		{
			xs=x;
			int i=0;
			while(i<m&&i<(l-k))
			{
				x=f(x,c,n);
				q=mul(q,abs(y-x),n);
				++i;
			}
			g=__gcd(q,n);
			k+=m;
		}
		l*=2;
	}
	if(g==n)
	{
		do
		{
			xs=f(xs,c,n);
			g=__gcd(abs(xs-y),n);
		}while(g==1);
	}
	return g;
}

int main() {
	map<ll,ll> fac;
	ll p;
	while(1)
	{
		ll n;
		cin>>n;
		if(n==0)
			break;
		fac.clear();
		while(n!=1)
		{
			p=brent(n);
			while(!fermant(p,20))
				p=brent(n);
			n/=p;
			fac[p]++;
		}
		for(auto i=fac.begin();i!=fac.end();++i)
			cout<<i->first<<"^"<<i->second<<" ";
		cout<<endl;
	}
	return 0;
}