Please Help Me

1

please help me
my code is given TLE
Question Link https://www.codechef.com/problems/CODIGO01

My Code:
#include<bits/stdc++.h>
#define lli long long int
#define fast ios_base::sync_with_stdio(0);cin.tie(0);
#define vi vector
#define pb push_back
using namespace std;
lli present(lli n,lli k)
{
lli cnt=0;
for(lli i=1;i<=n;i++)
{
if(n%i==0)
{
if((i&(1<<(k-1))))
cnt+=1;
}
}
return cnt;
}
int main()
{
fast
lli t;
cin>>t;
while(t–)
{
lli n,k;
cin>>n>>k;
cout<<present(n,k)<<endl;
}
}

2

You are running a loop of size N to factorize a number N.

There are T=1000 test cases.
Complexity of your solution is O(T*N) which is huge.

You can use better factorization algorithms:
For example, Instead of checking all numbers till N, you can check till square root of N. That will give a O(T*sqrt(N)) solution which should be enough to pass.

1 Like
3

Thank u

1 Like
5
6

Instead of running loop from 1 to n u can run from 1 to sqrt(n) and then check if n is divisible by i as well as n/i increment by 2 else divisible only by 1 of i or n/i then increment by 1. Also give a condition that i!=n/i

1 Like