FRCTNS - Editorial

PROBLEM LINK:

Practice
Div-2 Contest
Div-1 Contest

Author: Ildar Gainullin
Tester: Nikolay Budin
Editorialist: Alei Reyes

DIFFICULTY:

Easy

PREREQUISITES:

Divisibility

PROBLEM:

A fraction \frac{a}{b} is good if it is equal to \frac{c}{c+1} for some positive integer c.

You are given one integer n. Find the number of pairs of integers a, b (1 \leq a, b \leq n), such that the fraction f(a,b)=\frac{a}{a + 1} \cdot \frac{b+1}{b} is good.

QUICK EXPLANATION

We are looking for pairs where f(a,b)=c/(c+1), for some integer c. Express c in terms of a and b, then simplify the numerator by taking the gcd with the denominator. It turns out that we only have to look for the divisors of a and a+1.

EXPLANATION:

In number theory problems, sometimes is useful to play with small values and try to discover some properties, you can even write a program that runs over all small values of (a,b) and spot some patterns. I wrote small fractions of the form a/(a+1) and its multiples a \cdot k / (a+1) \cdot k, then I simplified the resulting f(a,b), and after making some conjectures about the behaviour of f(a,b), I performed the following algebraic analysis.

A good fraction is always smaller than 1, therefore \frac{a}{a+1} \cdot \frac {b+1}{b} \lt 1, after simplifying we get that a \lt b.

We are interested in pairs (a, b) such that there exists an integer c where \frac{a}{a+1} \cdot \frac{b+1}{b} = \frac{c}{c+1}. Let’s isolate the term c in function of a and b:

c = \frac{a \cdot b + a}{b-a}

Since a \lt b, we can write b=a+d, for some positive integer d. The expression for c now becomes:

c=\frac{a \cdot (a+d+1)}{d}

Let’s simplify common factors between each member of the numerator with the denominator:

  • We can simplify at most x=gcd(a,d) from the first term.
  • We can simplify at most y=gcd(a+d+1,d) from the second term. By the euclidean algorithm we know that gcd(a,b)=gcd(b,a-b), therefore y=gcd(a+1,d).

That means that to make c an integer, we can set d = x' \cdot y', where x' is any divisor of a, and y' any divisor of a+1. Since a and a+1 are coprime, they don’t have common divisors, and we’ll always get different values for d.

Let’s brute force all integers a from 1 to n, iterate over each divisors x' of a and count the valid values of y'. Note that b \leq n, therefore a + x' \cdot y' \leq n, that means we have to count only the y' \leq (n-a)/x'. If we store the divisors of each integer in increasing order in a vector, we can count all such y' with binary search, or two pointers.

SOLUTIONS:

Setter's Solution
const int N = 1e6 + 20;

int d[N];

int main() {
  for (int i = 1; i < N; i++) {
    for (int j = i; j < N; j += i) {
      d[j]++;
    }
  }
  int n;
  cin >> n;
  ll ans = 0;
  for (int i = 1; i <= n; i++) {
    ans += d[i] * (ll) d[i + 1] / 2 - 1;
  }
  cout << ans << '\n';
}
Tester's Solution
void solve() {
  int n;
  cin >> n;
  vector<int> sieve(n + 2);
  for (int i = 2; i <= n; ++i) {
    if (!sieve[i]) {
      for (int j = i; j <= n; j += i) {
        sieve[j] = i;
      }
    }
  }
  ll ans = 0;
  gp_hash_table<int, int> cnt;

  auto find_divs = [&](vector<int>& divs, int num) {
    divs.clear();
    cnt.clear();
    while (num > 1) {
      cnt[sieve[num]]++;
      num /= sieve[num];
    }
    divs.push_back(1);
    for (pii p : cnt) {
      int sz = szof(divs);
      for (int q = 0; q < sz * p.ss; ++q) {
        divs.push_back(divs[q] * p.ff);
      }
    }
    sort(divs.begin(), divs.end());
  };

  vector<int> cur_divs = {1};
  vector<int> next_divs = {1, 2};
  for (int i = 1; i < n; ++i) {
    int c = szof(next_divs);
    for (int q = 0; q < szof(cur_divs); ++q) {
      while (c > 0 && i + (ll) next_divs[c - 1] * cur_divs[q] > n) {
        --c;
      }
      ans += c;
    }
    
    if (i < n - 1) {
      swap(next_divs, cur_divs);
      find_divs(next_divs, i + 2);
    }
  }

  cout << ans << "\n";
}

VIDEO EDITORIAL:

8 Likes

Man , How could this be an easy question , when it had AC submission<40

23 Likes

Maybe, difficulty is relative. Easy for 7 stars.

14 Likes

Time limit was to tight. My nlogn solution gets 1.01s and therefore TLE. Though a nice problem…

2 Likes

I think that the time limit was quite strict. My TLE solution in the contest (https://www.codechef.com/viewsolution/39870062) gave AC after micro memory optimizations (here: https://www.codechef.com/viewsolution/39891388).

4 Likes

I really liked the problemset of contest!

2 Likes

how this setter’s solution is giving right answer like he didn’t checked for the condition
y’≤(n−a)/x’ and he directly did d[i] * (ll) d[i + 1] / 2 - 1;
like I am not getting how this is possible he didnt even checked the condition
.

1 Like

Setter’s solution is something different, small and elegant…
Please check these points to understand this -

  1. Number of divisors of n*(n+1) = div[n]*div[n+1] (it is because gcd(n,n+1)==1)
  2. We can pair divisors of n*(n+1)
    In every pair, one divisor is <=n and other is greate than n
  3. Number of divisors of n*(n+1) less than n -
    (div[n]*div[n+1])/2 - 1 (-1 is to remove n)
  4. Number of good pairs of type (a,n) where (1<=a<n) =
    no. of divisors of n*(n+1) which are less than n
13 Likes

Can someone explain as to why this code of mine is verdicted as tle for last test cases :
as far as i think its complexity is nlog(logn) :

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
vectorv[1000002];
void solve(){
ll i,n,j;
scanf("%lld",&n);

for(i=1;ii<100002;i++){
for(j=i;j<100002;j+=i){
if(i
i<=j){
v[j].push_back(i);
if(j!=i*i)
v[j].push_back(j/i);
}
}
}
for(i=1;i<100002;i++)sort(v[i].begin(),v[i].end());

ll ans=0;
for(i=1;i<=n;i++){
for(j=0;j<v[i].size();j++){
ll u=v[i][j];
ll x=(n-i)/u;
ll lb=upper_bound(v[i+1].begin(),v[i+1].end(),x)-v[i+1].begin();
ans+=(lb);

   }

}
printf("%lld",ans);

}
int main()
{

ll t;
t=1;
while(t–){
solve();
}
}

Any help will be appreciated…

Thanks that is much helpful …

for(i=1;i<100002;i++)sort(v[i].begin(),v[i].end());

Here only you do nlogn work

ya thats right but why nlong is failing

i think v[i] is storing factors and atmost size of v[i] is <140 hence its nlog(140) close to 7*n

For finding the divisors of a number first I used (prime factors + recursion). This gave TLE in subtask 3. Then I used (prime factors + iterative version) to find the divisors. It passed all the test cases. What is the time complexity of both the methods? The iterative one : https://www.codechef.com/viewsolution/39900526

I think this might be the possible explanation of setter’s solution:-
for valid pair ( a , b )
–>(a/(a+1)((b+1)/b)=c/(c+1)
–>c=(a
(b+1))/(b-a);
–>let k=b-a ,-> a=b-k, also implies b>a ,thus 0<k<b
–>c=((b-k)(b+1))/k;
–>for making c to be +ve integer k must be divisor of numerator.
–>thus we have to find such k ,such that gcd( (b-k) * (b+1) ,k)=k (as numerator!=0 as c is +ve int)
–>thus we have to find such k ,such that gcd( b * b + b - (b+1)k , k )=k
–>thus we have to find such k ,such that gcd( b * b + b , k )=k (as gcd( x , y )=gcd( x+my , y) for any integer m, here m=b+1)
–>thus we have to find such k ,such that gcd( b * (b+1) ,k)=k
–>thus we have to find such k ,such that k divides( b * ( b+1) )
–>k can be any divisor ( b * (b+1) ) that it is in range 0<k<b
since( gcd ( b, b+1 )=1)
–>divisors[a
b]=divisors[a]divisors[b] if( gcd ( a , b ) =1) {here, divisors[i]=no. of divisors of i}
for eg a=(p1^a1) * (p2^a2) ; b=(p3^a2) * (p4^a4) {where pi’s are prime no. and ai’s +ve integer, since gcd ( a , b )=1,thus pi’s in ‘a’ not equal pj’s in ‘b’}
a * b = (p1^a1) * (p2^a2) * (p3^a2) * (p4^a4)
divisors[a * b]=[ (a1+1) * (a2+1) ] * [ (a3+1) * (a4+1) ]
divisors[a * b]=divisors[a] * divisors[b]
divisors[b*(b+1)]=divisors[b]divisors[b+1]
–>half of the divisors of b * (b+1) will be <= b
for eg:- let x be valid divisor of b
(b+1) then
if(x>b)
then y=(b
(b+1))/x must exist and it will be y <= b {1/x < 1/b --> (b*(b+1)/x < b+1 --> y < b+1 --> y <=b }
else if(x<=b)
then y=(b*(b+1))/x must exist and it will be y > b {1/x >= 1/b --> (b*(b+1)/x >= b+1 --> y >= b+1 --> y >b }
–>we required divisor to be < b. therefore [k = (divisors[b] * divisors[b+1])/2 - 1]. {-1 as b is already divisor of b*(b+1) and also b<=b}
–>for a given b no. of k denotes no. of valid pair( a , b ) where a must belongs [1,b-1] as k=b-a
–>no. of valid pair having integer <= n will sum of ( (divisors[i] * divisors[i+1] )/2 -1) for every i belongs to [1,n]

please correct me if I am wrong.

4 Likes

Thanks for explaining @mananghetia !

i was trying to find some other approach to this question…i was trying this code->

ll t = 1;
    // cin >> t;
    while (t--) {
        ll n, cnt = 0;
        cin >> n;
        ll i = 1;
        f(i, 1, n) {
            f(j, 1, i + 2) {
                if (j + i > n) {
                    // flag = 1;
                    break;
                }
                else if (i == j)continue;
                else {
                    // cout << i << " " << j << endl;
                    cnt++;
                }
            }

        }
        print(cnt);

can someone provide a test case where it will fail?

Thanks, that was really helpful.

Thanks for the explanation. Can you help me understand it completely though.

We have the following conditions to satisfy -:

  • b = a + d
  • a < b <= N

We are iterating/fixing over all a and trying to find number of d. There are two conditions that d must satisfy.

  1. d | a.(a+1) for m to be a positive integer.
  2. a+d <= N for b to be within bounds.

Finding number of factors of a.(a+1) helps with #1. How is the second condition guaranteed with ensuring d <= a?

In Editorial explanation, necessary and sufficient conditions for (a,b) to be good pair is

  1. 1<=a<b<=N
  2. (b-a) | a.(a+1)

But in setter’s solution, there is slight variations of conditions.
It can be also proved that following conditions are necessary and sufficient for (a,b) to be good pair

  1. 1<=a<b<=N
  2. (b-a) | b.(b+1)

answer = 0
for all b from 1 to N
{
answer+=( number of divisors of b*(b+1) less than b)
}

2 Likes