FRCTNS - Editorial

Can someone please explain what is wrong with my approach. An example n where it fails would be highly appreciated .
Code:

#include <bits/stdc++.h>
using namespace std;

int fact(int n){
int count =0;
for(int i= 1; i*i <= n; ++i){
if(n%i == 0){
if(i != n/i) count+=2;
else count++;
}
}
return count;
}
int main() {
int n;
cin>>n;
unsigned long long int count = 1;
if(n == 1) cout<<0;
else if(n == 2) cout<<1;
else{
int prev_fact = 2; //factors of 2 as we start from n = 3
for(int i = 3; i <= n; ++i){
//for each i find fact(i+1) + fact(i) -3
// -3 because
//1 is common factor(take it only once)
//i canā€™t be a solution
//i+1 canā€™t be a solution
int curr_fact = fact(i+1);
count += curr_fact + prev_fact -3;
prev_fact = curr_fact;
}
cout<<count;
}
return 0;
}

Link of my code: https://www.codechef.com/viewsolution/39919169

What I am doing here (in else part) is
Iterate i from 3 to n
and for each i
the answer accumulates as fact(i+1)+fact(i)-3
-3 because
1 is common (take it only once)
i canā€™t be a solution
i+1 canā€™t be a solution

For example n = 5
we start from
i = 1 => 0 (0 pairs possible)
i = 2 => 1 (1 pair possible)
so we directly initialize count = 0+1 = 1;
and from below the else part works
i = 3 => 2
count += f(4)+f(3) -3 = 3+2-3 = 2

i = 4 => 2
count += f(5) + f(4) -3= 2 + 3 -3 = 2

i = 5 => 3
count += f(6) + f(5) -3 = 4+2-3 = 3

(here f(x) = number of factors of x)

therefore the answer is 1+2+2+3 = 8
Can someone please explain where I am wrong/ give a test case where it fails?

Can anyone expain the setterā€™s solution

Thank you , i was thinking why half of divisors of n*(n+1) is <= n , your explanation helped me.

The setterā€™s Solution is elegant. :star_struck:

In the editorial , we arrived at the necessary conditons

  1. d = b - a , can only be the product of divisors of a , a+1.
  2. Since we have to satisfy the condition 1 <= a < b <= n , the dvisors product , d <= (n-a)

We can rewrite the necessary conditions as follows

  1. gcd(a,d) => gcd(a+d,d) => gcd(b,d)

  2. gcd(a+d+1,d) => gcd(b+1,d)

  3. d = b - a , can only be the product of divisors of b , b+1

  4. Since we have to satisfy the condition 1 <= a < b <= n , the dvisors product , d <= b-1 ( if d >= b , we will get ā€˜aā€™ values in 0 and negative integers. )

For more details see @mananghetia comment

I am unable to understand this divide by 2 part

Can you explain it further. I am not able to understand the setterā€™s approach.