Given three integers A, B, C, the task is to find
?Ai=1 ?Bj=1?Ck=1 d(i.j.k), where d(x) is the number of divisors of x. Answer can be very large, So, print answer modulo 109+7.
Examples:
Input: A = 2, B = 2, c = 2
Output: 20
Explanation: d(1.1.1) = d(1) = 1;
d(1·1·2) = d(2) = 2;
d(1·2·1) = d(2) = 2;
d(1·2·2) = d(4) = 3;
d(2·1·1) = d(2) = 2;
d(2·1·2) = d(4) = 3;
d(2·2·1) = d(4) = 3;
d(2·2·2) = d(8) = 4.
Input: A = 5, B = 6, C = 7
Output: 1520
Approach:
- Find the number of divisors of all numbers in the range [1, N]
- Run three nested loops with iterators i, j, k starting from 1 to N
- Then find d(i.j.k) using pre computed number of divisors.
Below is the implementation of the above approach:
C++
#include <bits/stdc++.h>using namespace std;#define N 100005#define mod 1000000007// To store the number of divisorsint cnt[N];// Function to find the number of divisors// of all numbers in the range 1 to nvoid Divisors(){ memset(cnt, 0, sizeof cnt); // For every number 1 to n for (int i = 1; i < N; i++) { // Increase divisors count for every number for (int j = 1; j * i < N; j++) cnt[i * j]++; }}// Function to find the sum of divisorsint Sumofdivisors(int A, int B, int C){ // To store sum int sum = 0; Divisors(); for (int i = 1; i <= A; i++) { for (int j = 1; j <= B; j++) { for (int k = 1; k <= C; k++) { int x = i * j * k; // Count the divisors sum += cnt[x]; if (sum >= mod) sum -= mod; } } } return sum;}// Driver codeint main(){ int A = 5, B = 6, C = 7; // Function call cout << Sumofdivisors(A, B, C); return 0;} |
Java
// Java code for above given approachclass GFG { static int N = 100005; static int mod = 1000000007; // To store the number of divisors static int cnt[] = new int[N]; // Function to find the number of divisors // of all numbers in the range 1 to n static void Divisors() { // For every number 1 to n for (int i = 1; i < N; i++) { // Increase divisors count for every number for (int j = 1; j * i < N; j++) { cnt[i * j]++; } } } // Function to find the sum of divisors static int Sumofdivisors(int A, int B, int C) { // To store sum int sum = 0; Divisors(); for (int i = 1; i <= A; i++) { for (int j = 1; j <= B; j++) { for (int k = 1; k <= C; k++) { int x = i * j * k; // Count the divisors sum += cnt[x]; if (sum >= mod) { sum -= mod; } } } } return sum; } // Driver code public static void main(String[] args) { int A = 5, B = 6, C = 7; // Function call System.out.println(Sumofdivisors(A, B, C)); }}/* This code contributed by PrinciRaj1992 */ |
Python3
# Python3 code for above given approachN = 100005mod = 1000000007# To store the number of divisors cnt = [0] * N; # Function to find the number of divisors # of all numbers in the range 1 to n def Divisors() : # For every number 1 to n for i in range(1, N) : # Increase divisors count # for every number for j in range(1, N // i) : cnt[i * j] += 1; # Function to find the sum of divisors def Sumofdivisors(A, B, C) : # To store sum sum = 0; Divisors(); for i in range(1,A + 1) : for j in range(1, B + 1) : for k in range(1, C + 1) : x = i * j * k; # Count the divisors sum += cnt[x]; if (sum >= mod) : sum -= mod; return sum; # Driver code if __name__ == "__main__" : A = 5; B = 6; C = 7; # Function call print(Sumofdivisors(A, B, C)); # This code is contributed by Ryuga |
C#
// C# code for above given approachusing System; class GFG { static int N = 100005; static int mod = 1000000007; // To store the number of divisors static int []cnt = new int[N]; // Function to find the number of divisors // of all numbers in the range 1 to n static void Divisors() { // For every number 1 to n for (int i = 1; i < N; i++) { // Increase divisors count for every number for (int j = 1; j * i < N; j++) { cnt[i * j]++; } } } // Function to find the sum of divisors static int Sumofdivisors(int A, int B, int C) { // To store sum int sum = 0; Divisors(); for (int i = 1; i <= A; i++) { for (int j = 1; j <= B; j++) { for (int k = 1; k <= C; k++) { int x = i * j * k; // Count the divisors sum += cnt[x]; if (sum >= mod) { sum -= mod; } } } } return sum; } // Driver code public static void Main(String[] args) { int A = 5, B = 6, C = 7; // Function call Console.WriteLine(Sumofdivisors(A, B, C)); }}// This code contributed by Rajput-Ji |
Javascript
<script> // Javascript code for above given approach let N = 100005; let mod = 1000000007; // To store the number of divisors let cnt = new Array(N); cnt.fill(0); // Function to find the number of divisors // of all numbers in the range 1 to n function Divisors() { // For every number 1 to n for (let i = 1; i < N; i++) { // Increase divisors count for every number for (let j = 1; j * i < N; j++) { cnt[i * j]++; } } } // Function to find the sum of divisors function Sumofdivisors(A, B, C) { // To store sum let sum = 0; Divisors(); for (let i = 1; i <= A; i++) { for (let j = 1; j <= B; j++) { for (let k = 1; k <= C; k++) { let x = i * j * k; // Count the divisors sum += cnt[x]; if (sum >= mod) { sum -= mod; } } } } return sum; } let A = 5, B = 6, C = 7; // Function call document.write(Sumofdivisors(A, B, C)); // This code is contributed by divyeshrabdiya07.</script> |
Output:
1520
Time Complexity: O((A * B * C) + N3/2)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
