CNTFRAC - Editorial

lavish_adm · March 2, 2022, 3:13pm

PROBLEM LINK:

Contest Division 1
Contest Division 2
Contest Division 3
Contest Division 4

Setter: Srikkanth R
Tester: Abhinav Sharma, Manan Grover
Editorialist: Lavish Gupta

DIFFICULTY:

Easy-Medium

PREREQUISITES:

You should be familiar with loops and the concept of Greatest Common Divisor.

PROBLEM:

Given an integer N, find the number of tuples (w, x, y, z) such that 1 \leq w, x, y, z \leq N and \frac{w}{x} + \frac{y}{z} is an integer.

For example, if N = 2, the tuple (1,2,1,2) satisfies both conditions, i.e. \frac{1}{2} + \frac{1}{2} = 1 is an integer, however (1,1,1,2) does not since \frac{1}{1} + \frac{1}{2} = 1.5 is not an integer.

QUICK EXPLANATION

Let us fix the values of w and x such that gcd(w, x) = 1. This will constraint the values z can take, and we can loop over the possible values of z to get the final answer.
What if w and x are not co-prime? We can consider all these pairs while looping over the above pairs of (w, x).

EXPLANATION:

The constraint of the problem suggests that we can fix 2 variables and then try to calculate the answer. Let us try to fix both w and x, and try to proceed further. We can fix other pairs also, like y and z, and get the answer.

So let us proceed by fixing w and x. Also, let w and x be co-prime. If not, they can be reduced to w' and x', such that w' and x' are co-prime and \frac{w}{x} = \frac{w'}{x'}. Hence, their contribution can be calculated when dealing with (w', x').

Now, we have gcd(w, x) = 1. So, for \frac{w}{x} + \frac{y}{z} to be an integer, z needs to be a multiple of x. Let us say that z = c \cdot x. Let us iterate over all the possible values of z.

So our problem becomes:

\frac{w}{x} + \frac{y}{c \cdot x} is an integer, which can be written as \frac{c \cdot w + y}{c \cdot x} is an integer.

Note that we know the values of c \cdot w and c \cdot x. The minimum value of y that satisfies the above equation will be y' = c \cdot x - (c \cdot w)\%(c \cdot x). The general value of y that will satisfy this equation can be represented as y = y' + \lambda \cdot (c \cdot x), with the constraint that y \leq N. We can calculate the number of valid y's as \frac{N - y'}{z} + 1.

Also note that this pair of (w, x) represents some other pairs which can be reduced to the form \frac{w}{x}. Number of such pairs will be min(N/w, N/x).

TIME COMPLEXITY:

O(N^2 \cdot \log{N}) for each test case.

SOLUTION:

Setter's solution

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define pii pair<int, int>
#define pb push_back
#define mp make_pair
#define F first
#define S second
const int MAX = 1010;
int f[MAX][MAX];
int main() {
	ios_base::sync_with_stdio(false); cin.tie(NULL); 
	int t; cin >> t;
	int n;
	while(t--){
		cin >> n;
		memset(f, 0, sizeof(f));
		for(int i = 1; i <= n; i++){
			for(int j = 1; j <= n; j++){
				int g = __gcd(i, j);
				int i1 = i / g, j1 = j / g;
				f[i1 % j1][j1]++;
			}
		}
		ll ans = 0;
		for(int j = 1; j <= n; j++){
			for(int i = 0; i < j; i++){
				ans += (ll)f[i][j] * f[(j - i) % j][j];
			}
		}
		cout << ans << endl;
	}
	return 0;
}

Tester-1's Solution

#include <bits/stdc++.h>
using namespace std;
 
 
/*
------------------------Input Checker----------------------------------
*/
 
long long readInt(long long l,long long r,char endd){
    long long x=0;
    int cnt=0;
    int fi=-1;
    bool is_neg=false;
    while(true){
        char g=getchar();
        if(g=='-'){
            assert(fi==-1);
            is_neg=true;
            continue;
        }
        if('0'<=g && g<='9'){
            x*=10;
            x+=g-'0';
            if(cnt==0){
                fi=g-'0';
            }
            cnt++;
            assert(fi!=0 || cnt==1);
            assert(fi!=0 || is_neg==false);
 
            assert(!(cnt>19 || ( cnt==19 && fi>1) ));
        } else if(g==endd){
            if(is_neg){
                x= -x;
            }
 
            if(!(l <= x && x <= r))
            {
                cerr << l << ' ' << r << ' ' << x << '\n';
                assert(1 == 0);
            }
 
            return x;
        } else {
            assert(false);
        }
    }
}
string readString(int l,int r,char endd){
    string ret="";
    int cnt=0;
    while(true){
        char g=getchar();
        assert(g!=-1);
        if(g==endd){
            break;
        }
        cnt++;
        ret+=g;
    }
    assert(l<=cnt && cnt<=r);
    return ret;
}
long long readIntSp(long long l,long long r){
    return readInt(l,r,' ');
}
long long readIntLn(long long l,long long r){
    return readInt(l,r,'\n');
}
string readStringLn(int l,int r){
    return readString(l,r,'\n');
}
string readStringSp(int l,int r){
    return readString(l,r,' ');
}
 
 
/*
------------------------Main code starts here----------------------------------
*/
 
const int MAX_T = 1e5;
const int MAX_N = 1e5;
const int MAX_SUM_LEN = 1e5;
 
#define fast ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0)
#define ff first
#define ss second
#define mp make_pair
#define ll long long
#define rep(i,n) for(int i=0;i<n;i++)
#define rev(i,n) for(int i=n;i>=0;i--)
#define rep_a(i,a,n) for(int i=a;i<n;i++)
 
int sum_len = 0;
int max_n = 0;
int yess = 0;
int nos = 0;
int total_ops = 0;

const ll mod = 998244353;

ll po(ll x, ll n ){ 
    ll ans=1;
     while(n>0){
        if(n&1) ans=(ans*x)%mod;
        x=(x*x)%mod;
        n/=2;
     }
     return ans;
}

int gc[1001][1001];

void pre(){
    rep_a(i,1,1001){
        rep_a(j,1,1001) gc[i][j] = __gcd(i,j);
    }
}

void solve()
{   

  int n = readIntLn(1,1000);
  sum_len += n;
  max_n = max(max_n, n);

  ll ans = 0;
  ll g,i1,j1,cnt_i,rem,bndry;

  rep_a(i,1,n+1){
    rep_a(j,1,n+1){
        g = gc[i][j];
        i1 = i/g;
        j1 = j/g;

        cnt_i = n/i1;
        ans += cnt_i*(n/j);
        rem = n%j;
        if(rem){
            bndry = (j-rem-1)/j1;
            ans += (g-bndry-1)*(cnt_i/g)+max(0ll, (cnt_i%g)-bndry);
        }
    }
  }

  cout<<ans<<'\n';
}
 
signed main()
{

    #ifndef ONLINE_JUDGE
    freopen("input.txt", "r" , stdin);
    freopen("output.txt", "w" , stdout);
    #endif
    fast;
    
    int t = 1;
    
    t = readIntLn(1,150);
    pre();
    
    for(int i=1;i<=t;i++)
    {    
       solve();
    }
   
    assert(getchar() == -1);
    assert(sum_len<=1e4);
 
    cerr<<"SUCCESS\n";
    cerr<<"Tests : " << t << '\n';
    cerr<<"Sum of lengths : " << sum_len << '\n';
    cerr<<"Maximum length : " << max_n << '\n';
    // cerr<<"Total operations : " << total_ops << '\n';
    //cerr<<"Answered yes : " << yess << '\n';
    //cerr<<"Answered no : " << nos << '\n';
}

Tester-2's Solution

#include <bits/stdc++.h>
using namespace std;
long long readInt(long long l, long long r, char endd) {
    long long x = 0;
    int cnt = 0;
    int fi = -1;
    bool is_neg = false;
    while (true) {
        char g = getchar();
        if (g == '-') {
            assert(fi == -1);
            is_neg = true;
            continue;
        }
        if ('0' <= g && g <= '9') {
            x *= 10;
            x += g - '0';
            if (cnt == 0) {
                fi = g - '0';
            }
            cnt++;
            assert(fi != 0 || cnt == 1);
            assert(fi != 0 || is_neg == false);
 
            assert(!(cnt > 19 || (cnt == 19 && fi > 1)));
        }
        else if (g == endd) {
            assert(cnt > 0);
            if (is_neg) {
                x = -x;
            }
            assert(l <= x && x <= r);
            return x;
        }
        else {
            assert(false);
        }
    }
}
 
string readString(int l, int r, char endd) {
    string ret = "";
    int cnt = 0;
    while (true) {
        char g = getchar();
        assert(g != -1);
        if (g == endd) {
            break;
        }
        cnt++;
        ret += g;
    }
    assert(l <= cnt && cnt <= r);
    return ret;
}
int main(){
  ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);
  #ifndef ONLINE_JUDGE
  freopen("input.txt", "r", stdin);
  freopen("output.txt", "w", stdout);
  #endif
  int t;
  t=readInt(1,150,'\n');
  int ns=0;
  while(t--){
    int n;
    n=readInt(1,1000,'\n');
    ns+=n;
    assert(ns<=10000);
    int ans = 0;
    int dp[n + 1][n + 1] = {};
    int cnt = 0;
    for(int i = 1; i < n + 1; i++){
      for(int j = 1; j < n + 1; j++){
        if(i % j == 0){
          cnt++;
        }else{
          int x = i, y = j;
          x %= y;
          int g = __gcd(x, y);
          x /= g;
          y /= g;
          dp[x][y]++;
        }
      }
    }
    for(int i = 1; i < n + 1; i++){
      for(int j = 1; j < n + 1; j++){
        if(i % j == 0){
          ans += cnt;
        }else{
          int x = i, y = j;
          x %= y;
          x = y - x;
          int g = __gcd(x, y);
          x /= g;
          y /= g;
          ans += dp[x][y];
        }
      }
    }
    cout<<ans<<"\n";
  }
  return 0;
}

Editorialist's Solution

#include<bits/stdc++.h>
#define ll long long
#define pll pair<ll ,ll>
using namespace std ;
const ll z = 998244353 ;
ll gcd(ll a , ll b){ if(b > a) return gcd(b , a) ; if(b == 0) return a ; return gcd(b , a%b) ;}
int g[2005][2005] ;

int main()
{

    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    #ifndef ONLINE_JUDGE
    freopen("inputf.txt" , "r" , stdin) ;
    freopen("outputf.txt" , "w" , stdout) ;
    freopen("error.txt" , "w" , stderr) ;
    #endif

    int t ;
    cin >> t ;

    
    for(int i = 0 ; i < 2005 ; i++)
        for(int j = 0 ; j < 2005 ; j++)
            g[i][j] = gcd(i , j) ;

    while(t--)
    {
        ll n ;
        cin >> n ;
        
        ll ans = 0 ;

        for(ll a = 1 ; a <= n ; a++)
        {
            for(ll b = 1 ; b <= n ; b++)
            {
                if(g[a][b] != 1)
                    continue ;

                ll cnt_1 = min(n/a , n/b) ;

                for(ll d = b ; d <= n ; d += b)
                {
                    ll l = d/b ;
                    ll min_c = (d - ((l*a)%d)) ;

                    if(min_c > n)
                        continue ;

                    ll cnt = (n - min_c)/d + 1;
                    ans += (cnt_1)*(cnt) ;
                    // cout << "a = " << a << " b = " << b << endl ;
                    // cout << "min_c = " << min_c << " max_c = " << n << " d = " << d << endl ;
                    // cout << "cnt = " << cnt << endl ;
                    // cout << endl ;
                }
            }
        }

        cout << ans << endl ;
    }

    return 0;
}

ersshiva · March 2, 2022, 5:50pm

Different idea:

Loop all x,w pairs and do count[reduced_fractional{x,w}} ++
reduced_fractional(x,w) → find fraction of x/w i/e (x%w, w) now reduce it to have gcd(num, den) = 1;
We have count of all pairs that give say i/j reduced fraction. note that (i/j < 1)
iterate on this map and pick one reduced fraction (i/j) → corresponding other reduced_fraction is (i-j/j)
do ans += count(i/j) * count(j-i/j)

number of reduced fractions = sum PHI(i) i=1 to n, PHI->euler totient function

TC: O(n^2 logn)
code: Hyzmdm - Online C++0x Compiler & Debugging Tool - Ideone.com

cubefreak777 · March 2, 2022, 6:31pm

Nice Problem, My Solution was slightly different.
Let’s look at fractional parts of the numbers instead of the numbers themselves. By fractional part of a number x I mean \{x\}=x- \left \lfloor{x}\right \rfloor where \left \lfloor{x}\right \rfloor is the greatest integer less than x.

Note that for p,q \in \mathbb{Z}, \displaystyle \left \{{\frac{p}{q}}\right \}=\frac{p \%q}{q}

For \displaystyle \frac{w}{x}+\frac{y}{z} to be an integer the fractional part of \displaystyle \frac{w}{x}+\frac{y}{z} should be zero which is possible in the following scenarios,

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \displaystyle\left \{{\frac{w}{x}}\right \}+\left \{{\frac{y}{z}}\right \}=0 \text{ or }1

Let’s look at the case when \displaystyle \left \{{\frac{w}{x}}\right \}+\left \{{\frac{y}{z}}\right \}=1

\ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \displaystyle \left \{{\frac{w}{x}}\right \}+\left \{{\frac{y}{z}}\right \}=\frac{w \%x}{x}+\frac{y \%z}{z}=1

\implies\boxed{\frac{x-w\%x}{x} =\frac{y\%z}{z}}

Now let’s solve the following subproblem.

For a given p ,q where p and q are coprime find the number of pairs (y,z) where 1 \le y,z \le N for which \displaystyle \frac{p}{q}=\frac{y \%z}{z}.

We can easily solve this subproblem in \mathcal{O}(N^2) time by iterating over all possible values of y and z. Say C_{p,q} is the answer for a given p,q

Now let’s fix x and w and then the problem just boils down to finding the number of pairs (y,z) for which \displaystyle\frac{x-w\%x}{x} =\frac{y\%z}{z} and since we’ve precomputed these values we can just pull out the value of C_{p,q} where \displaystyle \frac{p}{q} is the reduced form the fraction \displaystyle \frac{x-w\%x}{x} and add it to the final answer.

The case when \displaystyle \left \{{\frac{w}{x}}\right \}+\left \{{\frac{y}{z}}\right \}=0 can be easily taken care off in a similar manner.

CODE FOR REFERENCE