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: 4

Input: 5
Output: 17

Input: 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:

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.

1. 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.
2. 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).)
• Print ans modulo 998244353 as the final result.

Below is the implementation of the above approach:

Time Complexity: O(√N)
Auxiliary Space: O(1)