This was the Question from lunchtime. I tried to optimize the code but still, I got 50 pts for this problem. Please, anyone, optimize my code.

The problem is in your for loop. In the worst case, you are moving from sqrt(m) + 1 to m, which is not fast (correct though). You should instead loop from 1 to sqrt(m). For example, if m = 25, then looping from sqrt(m) + 1 to m takes 25 - 5 - 1= 19 steps, while looping from 1 to sqrt(m) just takes 5 steps.

Also, you need not clear the vector every time as you are redeclaring it every time.

Please provide me the optimized code.

When a = 1, your code will always output 0, but it is not the case with the answer.

Eg.

Input

1

1 432874

Output

7

216437 399576 416225 432848 432861 432872 432873

But your code returns 0.

broâ€¦can you explain me the approach to the problem EVIPROâ€¦I have seen many submissionsâ€¦in awivh they are adding n(n-1)/2 to the answer if s[i] and s[i+1] are sameâ€¦and adding n if notâ€¦I want to askâ€¦how thisâ€¦formulaâ€¦came?

Basic idea is:

- If s[i] and s[i+1] are same, they must be in the same chosen substring, or both must not be in the chosen substring.
- Otherwise, one must be in chosen substring while other must not be in that.

We just need to count the number of ways to make that happen.

the term n * (n+1) / 2 comes from the number of sequences to left of s[i] or to right of s[i+1] for ensuring case-1, where none of s[i] and s[i+1] is in chosen substring.

My code: https://www.codechef.com/viewsolution/28530167

Itâ€™s purely a combinatorics problem.

please see what is wrong with this code:

#include<bits/stdc++.h>

#define ll long long

using namespace std;

int main()

{

ll t,m,n,a,i,s;

cin>>t;

while(tâ€“){

cin>>a>>m;

vector v;

s=m/a;

//i=s;

if((m-s*a)==0 && a!=1){
cout<<0<<endl;
cout<<endl;
}
else{
for(i=sqrt(m)+1; i<=(m/a); i++)
{
if( ((m-i*a)!=0) && (i%(m - i*a))==0 )

v.push_back(i);

```
}
//sort(v.begin(), v.end(), greater<int>());
ll size=v.size();
//ll* arr=new ll[size];
//ll c=0;
//for(auto i=v.begin();i!=v.end();++i)
// arr[c++]=*i;
//sort(arr, arr+size);
cout<<size<<endl;
for(i=0;i<size;i++)
cout<<v[i]<<" ";
cout<<endl;
v.clear();
}
}
```

}

thanx a lot bro