DCP-238: Even divisor

Dev Skill archived problems can be discussed here.

DCP-238: Even divisor

by ranacseiu » Tue Feb 28, 2017 10:34 am

Give Some Critical Input . Getting TLE....

#define mx 10000000
using namespace std;
bool prime[mx+1];
int i,j,lim,r=1;
int store[664579];
void seive()
{
lim=sqrt(mx);
prime[0]=1;prime[1]=1;
prime[2]=0;
for(i=3;i<=lim;i+=2)
{
if(prime[i])
continue;
for(j=i*i;j<=mx;j+=i)
prime[j]=1;
}
for(i=3;i<=mx;i+=2)
{
if(prime[i]==0)
store[r++]=i;
}
}
map<long,long>mll,mpp;
long give_me_ans(long n)
{
long res=0,ans=0,cnt=0;
if(mll[n]==5)
{
return mpp[n];
}
mll[n]=5;
if(n%2==1)
{
return mpp[n]=0;
}
else
{
cnt=1;
if(n%2==0)
{
while(n%2==0)
{
if(n==0)
break;
n/=2;//cout<<"n= "<<n<<" "<<j<<endl;
cnt*=2;
res+=cnt;
}
}
ans=res;
int j=1;
while(1)
{//cout<<j<<endl;
if(n/store[j]==0)
break;
cnt=1,res=1;
if(n%store[j]==0)
{
if(n==0)
break;
cnt=1;
while(n%store[j]==0)
{
if(n==0)
break;
n/=store[j];//cout<<"n= "<<n<<" "<<j<<endl;
cnt*=store[j];
res+=cnt;
}
}
ans*=res;
j+=1;
}
return mpp[n]=ans;
}
}
int main()
{
seive();
ios_base::sync_with_stdio(false);
long tc;
sci(tc);
rep2(z,tc)
{
long num;
sci(num);
long pss=0;
pss=give_me_ans(num);
printf("%ld\n",pss);
}
return 0;
}
 
Posts: 1
Joined: Tue Feb 28, 2017 9:57 am

Who is online
Users browsing this forum: No registered users and 1 guest
cron