Counting triples with product condition
Given a positive integer N (1 ≤ N ≤ 10^9), find the number of triples of positive integers (x, y, z) modulo 998244353 that satisfy the condition: the product of any two numbers from the triple (x, y, z) should be less than or equal to N. The task is to count the number of triples (x, y, z) such that 1 ≤ x, y, z ≤ N, and the products xy, yz, and zx are all less than or equal to N. Your task is to compute this count modulo 998244353 and output the result.
Examples:
Input: 2
Output: 4Input: 5
Output: 17Input: 998244353
Output: 727512986
Naive Approach: By brute force approach we can run three nested for loops to get our answer by is much more time-consuming as N<=109 so it gives us a time limit to exceed we have a more efficient solution for this problem.
Below is the code for the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; const int MOD = 998244353; // Function to count the number of valid triples int countValidTriples( int N) { int count = 0; // Iterate over all possible values // of x, y, and z for ( int x = 1; x <= N; x++) { for ( int y = 1; y <= N; y++) { for ( int z = 1; z <= N; z++) { // Check if the condition is // satisfied: x*y, y*z, and z*x // should be less than or equal // to N if (x * y <= N && y * z <= N && z * x <= N) { count++; // Take modulo 998244353 // to ensure the result is // within the given range count %= MOD; } } } } return count; } // Drivers code int main() { // Define the value of N int N = 5; // Call the countValidTriples function // to get the count of valid triples int result = countValidTriples(N); // Display the result cout << "Count of valid triples: " << result << endl; return 0; } |
Java
// Java code for the above approach class GFG { static final int MOD = 998244353 ; static int countValidTriples( int N) { int count = 0 ; // Iterate over all possible values // of x, y, and z for ( int x = 1 ; x <= N; x++) { for ( int y = 1 ; y <= N; y++) { for ( int z = 1 ; z <= N; z++) { // Check if the condition is // satisfied: x*y, y*z, and z*x // should be less than or equal // to N if (x * y <= N && y * z <= N && z * x <= N) { count++; // Take modulo 998244353 // to ensure the result is // within the given range count %= MOD; } } } } return count; } public static void main(String[] args) { // Define the value of N int N = 5 ; // Call the countValidTriples function // to get the count of valid triples int result = countValidTriples(N); // Display the result System.out.println( "Count of valid triples: " + result); } } // This code is contributed by ragul21 |
Python3
MOD = 998244353 # Function to count the number of valid triples def countValidTriples(N): count = 0 # Iterate over all possible values # of x, y, and z for x in range ( 1 , N + 1 ): for y in range ( 1 , N + 1 ): for z in range ( 1 , N + 1 ): # Check if the condition is # satisfied: x*y, y*z, and z*x # should be less than or equal # to N if x * y < = N and y * z < = N and z * x < = N: count + = 1 # Take modulo 998244353 # to ensure the result is # within the given range count % = MOD return count # Drivers code if __name__ = = "__main__" : # Define the value of N N = 5 # Call the countValidTriples function # to get the count of valid triples result = countValidTriples(N) # Display the result print ( "Count of valid triples:" , result) |
C#
// C# code for the above approach using System; class GFG { static readonly int MOD = 998244353; static int countValidTriples( int N) { int count = 0; // Iterate over all possible values // of x, y, and z for ( int x = 1; x <= N; x++) { for ( int y = 1; y <= N; y++) { for ( int z = 1; z <= N; z++) { // Check if the condition is // satisfied: x*y, y*z, and z*x // should be less than or equal // to N if (x * y <= N && y * z <= N && z * x <= N) { count++; // Take modulo 998244353 // to ensure the result is // within the given range count %= MOD; } } } } return count; } public static void Main( string [] args) { // Define the value of N int N = 5; // Call the countValidTriples function // to get the count of valid triples int result = countValidTriples(N); // Display the result Console.WriteLine( "Count of valid triples: " + result); } } // This code is contributed by Sakshi |
Javascript
// JavaScript code for the above approach: const MOD = 998244353; // Function to count the number of valid triples function countValidTriples(N) { let count = 0; // Iterate over all possible values // of x, y, and z for (let x = 1; x <= N; x++) { for (let y = 1; y <= N; y++) { for (let z = 1; z <= N; z++) { // Check if the condition is // satisfied: x*y, y*z, and z*x // should be less than or equal // to N if (x * y <= N && y * z <= N && z * x <= N) { count++; // Take modulo 998244353 // to ensure the result is // within the given range count %= MOD; } } } } return count; } // Drivers code // Define the value of N const N = 5; // Call the countValidTriples function // to get the count of valid triples const result = countValidTriples(N); // Display the result console.log( "Count of valid triples: " + result); // This code is contributed by prasad264 |
Count of valid triples: 17
Time Complexity: O(N3)
Auxiliary Space: O(1)
Efficient Approach: This is an efficient approach to solving the problem. It calculates the number of valid triples (x, y, z) using a mathematical formula based on the value of N.
- When max(x, y, z) ≤ N: In this case, the condition is always satisfied because all the numbers in the triple are less than or equal to N. Therefore, the number of such triples (x, y, z) is N^3.
- When max(x, y, z) > N: We can observe that if any number exceeds N, the condition will not be satisfied. So, we can assume that only one variable takes the maximum value, let’s say x > y, z. When x is fixed, the condition is equivalent to y, z ≤ [N/x], where [N/x] represents the floor division of N by x. Considering that there are three choices for which x, y, and z take the maximum value, the total number of triples that satisfy the condition is 3 times the summation of [N/i]^2, where i ranges from M+1 to N.
Since there are only O(√N) different values of N/i, we can optimize the computation by calculating [N/i]^2 for each i and summing them up. Finally, we multiply the result by 3 to account for the three possible choices for the maximum value.
To summarize, the count of valid triples (x, y, z) can be calculated as follows: count = N^3 + 3 * Σ[N/i]^2, where i ranges from M+1 to N. (Note that we need to perform all calculations modulo 998244353 to ensure the result is within the given range.)
Steps to implement the above approach:
- Initialize variables n (the given positive integer), ans (to store the result), b = 0, c = 0.
- Initialize ans with the square root of n, computed using the int(sqrt(n)) function.
- Iterate from i = 1 to i * i <= n.
- Inside the loop, do the following:
- Increment ans by 3 times (n / i).
- (This accounts for the valid triples where x, y, or z is equal to i. Since n / i gives the largest possible value for the other two numbers, multiplying it by 3 covers all the valid combinations.)
- Check if n divided by i is greater than or equal to i.
- If true, decrement ans by 3.
- (This step ensures that we don’t count the same triple multiple times, where x, y, and z are distinct numbers. By decrementing ans by 3, we eliminate the cases where all three numbers are equal to i, which were counted in the previous step.)
- Increment ans by 6 times ((n / i) – i) * (i – 1).
- (This accounts for the valid triples where two numbers are equal to i and the third number ranges from i + 1 to (n / i). Let’s break down this formula:
- (n / i – i) gives the number of distinct values the third number can take, ranging from i + 1 to (n/i). For example, if i = 2 and n = 10, the possible values for the third number are 3, 4, and 5.
- (i – 1) represents the number of valid pairs (y, z) where both y and z are less than or equal to i. This accounts for the combinations where either y or z is equal to i. For example, if i = 2, the valid pairs are (1, 1), (1, 2), and (2, 1).
- Multiplying (n / i – i) by (i – 1) gives the total number of valid triples for a particular value of i. This term accounts for the fact that the third number can be paired with (i – 1) different values.
- Multiplying the result by 6 accounts for all possible combinations where two numbers are equal to i. Since there are (n / i – i) * (i – 1) valid triples for each value of i, multiplying by 6 ensures that we count all possible permutations of the triples (x, y, z).)
- Increment ans by 3 times (n / i).
- Print ans modulo 998244353 as the final result.
Below is the implementation of the above approach:
C++
// C++ code for the above approach: #include <bits/stdc++.h> using namespace std; // Function to count the number of valid triples void countValidTriples( int n, int ans, int b, int c) { // Increment ans by the square root of n ans += int ( sqrt (n)); // Iterate from i = 1 to i * i <= n for ( int i = 1; i * i <= n; i++) { // Increment ans by 3 times (n / i) ans += 3 * (n / i); // Check if n divided by i is greater // than or equal to i if (n / i >= i) // If true, decrement ans by 3 ans -= 3; // Increment ans by 6 times ((n / i) - i) * (i - 1) // Please follow the given steps // for clarification ans += 6 * (n / i - i) * (i - 1); } cout << ans % 998244353 << endl; } // Drivers code int main() { int n = 5; int ans = 0, b = 0, c = 0; // Function Call countValidTriples(n, ans, b, c); return 0; } |
Java
// Java code for the above approach: class GFG { // Function to count the number of valid triples static void countValidTriples( int n, int ans, int b, int c) { // Increment ans by the square root of n ans += ( int )Math.sqrt(n); // Iterate from i = 1 to i * i <= n for ( int i = 1 ; i * i <= n; i++) { // Increment ans by 3 times (n / i) ans += 3 * (n / i); // Check if n divided by i is greater // than or equal to i if (n / i >= i) // If true, decrement ans by 3 ans -= 3 ; // Increment ans by 6 times ((n / i) - i) * (i - // 1) Please follow the given steps for // clarification ans += 6 * (n / i - i) * (i - 1 ); } System.out.println(ans % 998244353 ); } // Drivers code public static void main(String[] args) { int n = 5 ; int ans = 0 , b = 0 , c = 0 ; // Function Call countValidTriples(n, ans, b, c); } } // This code is contributed by ragul21 |
Python3
import math # Function to count the number of valid triples def countValidTriples(n): ans = 0 # Increment ans by the square root of n ans + = int (math.sqrt(n)) # Iterate from i = 1 to i * i <= n for i in range ( 1 , int (math.sqrt(n)) + 1 ): # Increment ans by 3 times (n / i) ans + = 3 * (n / / i) # Check if n divided by i is greater # than or equal to i if n / / i > = i: # If true, decrement ans by 3 ans - = 3 # Increment ans by 6 times ((n / i) - i) * (i - 1) ans + = 6 * (n / / i - i) * (i - 1 ) print (ans % 998244353 ) # Drivers code if __name__ = = "__main__" : n = 5 # Function Call countValidTriples(n) #Contributed by Aditi Tyagi |
C#
using System; class Program { // Function to count the number of valid triples static void CountValidTriples( int n, int ans, int b, int c) { // Increment ans by the square root of n ans += ( int )Math.Sqrt(n); // Iterate from i = 1 to i * i <= n for ( int i = 1; i * i <= n; i++) { // Increment ans by 3 times (n / i) ans += 3 * (n / i); // Check if n divided by i is greater than or equal to i if (n / i >= i) { // If true, decrement ans by 3 ans -= 3; } // Increment ans by 6 times ((n / i) - i) * (i - 1) ans += 6 * (n / i - i) * (i - 1); } Console.WriteLine(ans % 998244353); } // Driver code static void Main( string [] args) { int n = 5; int ans = 0, b = 0, c = 0; // Function Call CountValidTriples(n, ans, b, c); } } |
Javascript
// JavaScript code for the above approach: // Function to count the number of valid triples function countValidTriples(n, ans, b, c) { // Increment ans by the square root of n ans += Math.floor(Math.sqrt(n)); // Iterate from i = 1 to i * i <= n for (let i = 1; i * i <= n; i++) { // Increment ans by 3 times (n / i) ans += 3 * Math.floor(n / i); // Check if n divided by i is greater // than or equal to i if (n / i >= i) // If true, decrement ans by 3 ans -= 3; // Increment ans by 6 times ((n / i) - i) * (i - 1) // Please follow the given steps // for clarification ans += 6 * (Math.floor(n / i) - i) * (i - 1); } console.log(ans % 998244353); } // Drivers code function main() { let n = 5; let ans = 0, b = 0, c = 0; // Function Call countValidTriples(n, ans, b, c); } // Execute the main function main(); // This code is contributed by akshitaguprzj3 |
17
Time Complexity: O(√N)
Auxiliary Space: O(1)