Techno Blender
Digitally Yours.


Technology

Quadruples for Sum and Product of Integers with XOR

By Ann Roberts
0 34


Given an integer N, the task is to find X and Y where X is the number of quadruples of positive integers (A, B, C, D) such that AB + CD = N, Y is the number of quadruples of positive integers (A, B, C, D) such that (A + B)(C + D) = N. Print X XOR Y.

Examples:

Input: N = 4
Output: 9
Explanation: First we count X, the number of quadruples of positive integers (A, B, C, D) such that AB + CD = N 

  • (A, B, C, D) = (1, 1, 1, 3)
  • (A, B, C, D) = (1, 1, 3, 1)
  • (A, B, C, D) = (1, 2, 1, 2)
  • (A, B, C, D) = (1, 2, 2, 1)
  • (A, B, C, D) = (1, 3, 1, 1)
  • (A, B, C, D) = (2, 1, 1, 2)
  • (A, B, C, D) = (2, 1, 2, 1)
  • (A, B, C, D) = (3, 1, 1, 1)

So, X = 8, Secondly we count Y, the number of quadruples of positive integers (A, B, C, D) such that (A + B)(C + D) = N 

  • (A, B, C, D) = (1, 1, 1, 1), So, Y = 1

Now, X XOR Y = 9

Input: N = 6
Output: 16

Approach: To solve the problem follow the below idea:

The main idea to solve the given problem is to find the number of quadruples of positive integers that satisfy the given equations, where X is the number of quadruples satisfying AB + CD = N, and Y is the number of quadruples satisfying (A + B)(C + D) = N. After finding X and Y, the XOR operation is performed between them to get the final result. This problem requires the use of mathematical techniques to derive formulas for X and Y, followed by their computation using a suitable algorithm.

Below are the steps for the above approach:

  • Create a function countDivisors(int n) that counts the number of divisors of n.
    • Initialize a variable cnt = 0.
    •  Iterate from i = 1 to sqrt(n).
      • Check if n is divisible by i, then check if n/i == i, increment cnt by 1, else increment count by 2.
    • Return cnt.
  • Create a function counttuples(int n) that counts the total number of quadruples of positive integers (A, B, C, D) such that AB + CD = N.
    • Initialize a variable cnt = 0.
    • Iterate from i = 2 to n-1.
      • Check if n is divisible by i, initialize two temporary variables temp1 = i-1 and temp2 = (n / i) – 1
      • Add temp1 * temp2 to cnt.
    • Return cnt.
  • Initialize two variables X and Y to zero.
  • Iterate from i = 1 to n-1.
    •  Calculate the number of divisors ‘a’ of i using the countDivisors(i) function.
    •  Calculate the number of divisors ‘b’ of (n – i) using the countDivisors(n – i) function.
    • Add a * b to X.
  • Find the number of quadruples Y of positive integers (A, B, C, D) such that (A + B)(C + D) = N using counttuples(n) function.
  • Print (X XOR Y).

Below is the implementation for the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

  

int countDivisors(int n)

{

    int cnt = 0;

    for (int i = 1; i * i <= n; i++) {

        if (n % i == 0) {

  

            

            

            if (n / i == i)

                cnt++;

  

            

            else

                cnt = cnt + 2;

        }

    }

    return cnt;

}

  

int counttuples(int n)

{

  

    int cnt = 0;

  

    

    

    

    

    for (int i = 2; i < n; i++) {

  

        

        

        if (n % i == 0) {

  

            

            

            

            int temp1 = i - 1;

            int temp2 = (n / i) - 1;

            cnt += (temp1 * temp2);

        }

    }

    return cnt;

}

  

int main()

{

    int n = 6;

  

    int X = 0;

    for (int i = 1; i < n; i++) {

        int a = countDivisors(i);

        int b = countDivisors(n - i);

        X += (a * b);

    }

    int Y = counttuples(n);

  

    cout << (X ^ Y) << endl;

    return 0;

}

Time Complexity: O(n^(3/2))
Auxiliary Space: O(1)


Given an integer N, the task is to find X and Y where X is the number of quadruples of positive integers (A, B, C, D) such that AB + CD = N, Y is the number of quadruples of positive integers (A, B, C, D) such that (A + B)(C + D) = N. Print X XOR Y.

Examples:

Input: N = 4
Output: 9
Explanation: First we count X, the number of quadruples of positive integers (A, B, C, D) such that AB + CD = N 

  • (A, B, C, D) = (1, 1, 1, 3)
  • (A, B, C, D) = (1, 1, 3, 1)
  • (A, B, C, D) = (1, 2, 1, 2)
  • (A, B, C, D) = (1, 2, 2, 1)
  • (A, B, C, D) = (1, 3, 1, 1)
  • (A, B, C, D) = (2, 1, 1, 2)
  • (A, B, C, D) = (2, 1, 2, 1)
  • (A, B, C, D) = (3, 1, 1, 1)

So, X = 8, Secondly we count Y, the number of quadruples of positive integers (A, B, C, D) such that (A + B)(C + D) = N 

  • (A, B, C, D) = (1, 1, 1, 1), So, Y = 1

Now, X XOR Y = 9

Input: N = 6
Output: 16

Approach: To solve the problem follow the below idea:

The main idea to solve the given problem is to find the number of quadruples of positive integers that satisfy the given equations, where X is the number of quadruples satisfying AB + CD = N, and Y is the number of quadruples satisfying (A + B)(C + D) = N. After finding X and Y, the XOR operation is performed between them to get the final result. This problem requires the use of mathematical techniques to derive formulas for X and Y, followed by their computation using a suitable algorithm.

Below are the steps for the above approach:

  • Create a function countDivisors(int n) that counts the number of divisors of n.
    • Initialize a variable cnt = 0.
    •  Iterate from i = 1 to sqrt(n).
      • Check if n is divisible by i, then check if n/i == i, increment cnt by 1, else increment count by 2.
    • Return cnt.
  • Create a function counttuples(int n) that counts the total number of quadruples of positive integers (A, B, C, D) such that AB + CD = N.
    • Initialize a variable cnt = 0.
    • Iterate from i = 2 to n-1.
      • Check if n is divisible by i, initialize two temporary variables temp1 = i-1 and temp2 = (n / i) – 1
      • Add temp1 * temp2 to cnt.
    • Return cnt.
  • Initialize two variables X and Y to zero.
  • Iterate from i = 1 to n-1.
    •  Calculate the number of divisors ‘a’ of i using the countDivisors(i) function.
    •  Calculate the number of divisors ‘b’ of (n – i) using the countDivisors(n – i) function.
    • Add a * b to X.
  • Find the number of quadruples Y of positive integers (A, B, C, D) such that (A + B)(C + D) = N using counttuples(n) function.
  • Print (X XOR Y).

Below is the implementation for the above approach:

C++

#include <bits/stdc++.h>

using namespace std;

  

int countDivisors(int n)

{

    int cnt = 0;

    for (int i = 1; i * i <= n; i++) {

        if (n % i == 0) {

  

            

            

            if (n / i == i)

                cnt++;

  

            

            else

                cnt = cnt + 2;

        }

    }

    return cnt;

}

  

int counttuples(int n)

{

  

    int cnt = 0;

  

    

    

    

    

    for (int i = 2; i < n; i++) {

  

        

        

        if (n % i == 0) {

  

            

            

            

            int temp1 = i - 1;

            int temp2 = (n / i) - 1;

            cnt += (temp1 * temp2);

        }

    }

    return cnt;

}

  

int main()

{

    int n = 6;

  

    int X = 0;

    for (int i = 1; i < n; i++) {

        int a = countDivisors(i);

        int b = countDivisors(n - i);

        X += (a * b);

    }

    int Y = counttuples(n);

  

    cout << (X ^ Y) << endl;

    return 0;

}

Time Complexity: O(n^(3/2))
Auxiliary Space: O(1)

FOLLOW US ON GOOGLE NEWS

Read original article here

Denial of responsibility! Techno Blender is an automatic aggregator of the all world’s media. In each content, the hyperlink to the primary source is specified. All trademarks belong to their rightful owners, all materials to their authors. If you are the owner of the content and do not want us to publish your materials, please contact us by email – [email protected]. The content will be deleted within 24 hours.
Ann Roberts 41603 posts 0 comments
Leave a comment
More Stories

M1 Mac and newer have an unpatchable vulnerability

5 Things about AI you may have missed today: GenAI to…

How the EU’s antitrust lawsuit against tech giant…

1 of 13,869