Given a number N, the task is to find the sum of all the perfect square divisors of numbers from 1 to N.
Examples:
Input: N = 5
Output: 9
Explanation: N = 5
Perfect square divisors of 1 = 1.
Similarly, perfect square divisors of 2, 3 = 1.
Perfect square divisors of 4 = 1, 4.
Perfect square divisors of 5 = 1 (of course for any prime only 1 will be the perfect square divisor)
So, total sum = 1+1+1+(1+4)+1 = 9.Input: N = 30
Output: 126Input: N = 100
Output: 910
Naive Approach: This approach is based on the approach implemented in this article
The above problem can be solved in O(N1/k) for any Kth power divisors, where N is the number up to which we have to find the sum. This is because, in this sum, every number will contribute floor(N/p) or int(N/p) times. Thus, while iterating through these perfect powers, we just need to add [p * int(N/p)] to the sum.
Time Complexity: O(?N)
Efficient Approach:
- Let us start from start = 2, find the largest range (start to end) for which floor(N/(start2)) = floor(N/(end2))
- The contribution of all perfect squares in the interval [start, end] will contribute floor(N/(start2)) times, hence we can do update for this range at once.
- Contribution for range [start, end] can be given as:
floor(N/(start2))*(sumUpto(end) – sumUpto(start-1))
- How to find range?
For a given value of start, end can be found by
sqrt(N/K), where K = floor(N/(start^2))
- Now the next range can be found by substituting start = end+1.
Time complexity: O(N1/3) as N/(x2) cannot take more than N1/3 different values for a fixed value of N.
Below is the implementation of the above approach:
C++
// C++ Program to find the// sum of all perfect square// divisors of numbers from 1 to N#include <bits/stdc++.h>using namespace std;#define MOD 1000000007#define int unsigned long long// Function for finding inverse// of a number iteratively// Here we will find the inverse// of 6, since it appears as// denominator in the formula of// sum of squares from 1 to Nint inv(int a){ int o = 1; for (int p = MOD - 2; p > 0; p >>= 1) { if ((p & 1) == 1) o = (o * a) % MOD; a = (a * a) % MOD; } return o;}// Store the value of the inverse// of 6 once as we don't need to call// the function again and againint inv6 = inv(6);// Formula for finding the sum// of first n squaresint sumOfSquares(int n){ n %= MOD; return (((n * (n + 1)) % MOD * (2 * n + 1)) % MOD * inv6) % MOD;}int sums(int n){ // No perfect square // exists which is // less than 4 if (n < 4) return 0; // Starting from 2, present value // of start is denoted here as // curStart int curStart = 2, ans = 0; int sqrtN = sqrt(n); while (curStart <= n / curStart) { int V = n / (curStart * curStart); // Finding end of the segment // for which the contribution // will be same int end = sqrt(n / V); // Using the above mentioned // formula to find ans % MOD ans += (n / (curStart * curStart) % MOD * (sumOfSquares(end) + MOD - sumOfSquares(curStart - 1))) % MOD; if (ans >= MOD) ans -= MOD; // Now for the next iteration // start will become end+1 curStart = end + 1; } // Finally returning the answer return ans;}// Driver Codeint32_t main(){ int input[] = { 5 }; for (auto x : input) { cout << "sum of all perfect" << " square divisors from" << " 1 to " << x << " is: "; // Here we are adding x // because we have not // counted 1 as perfect // squares so if u want to // add it you can just add // that number to the ans cout << x + sums(x) << endl; } return 0;} |
Java
// Java program to find the// sum of all perfect square// divisors of numbers from 1 to Nimport java.util.*;class GFG{static final int MOD = 7;// Function for finding inverse// of a number iteratively// Here we will find the inverse// of 6, since it appears as// denominator in the formula of// sum of squares from 1 to Nstatic int inv(int a){ int o = 1; for(int p = MOD - 2; p > 0; p >>= 1) { if ((p & 1) == 1) o = (o * a) % MOD; a = (a * a) % MOD; } return o;}// Store the value of the inverse// of 6 once as we don't need to call// the function again and againstatic int inv6 = inv(6);// Formula for finding the sum// of first n squaresstatic int sumOfSquares(int n){ n %= MOD; return (((n * (n + 1)) % MOD * (2 * n + 1)) % MOD * inv6) % MOD;}static int sums(int n){ // No perfect square // exists which is // less than 4 if (n < 4) return 0; // Starting from 2, present value // of start is denoted here as // curStart int curStart = 2, ans = 0; int sqrtN = (int)Math.sqrt(n); while (curStart <= n / curStart) { int V = n / (curStart * curStart); // Finding end of the segment // for which the contribution // will be same int end = (int)Math.sqrt(n / V); // Using the above mentioned // formula to find ans % MOD ans += (n / (curStart * curStart) % MOD * (sumOfSquares(end) + MOD - sumOfSquares(curStart - 1))) % MOD; if (ans >= MOD) ans -= MOD; // Now for the next iteration // start will become end+1 curStart = end + 1; } // Finally returning the answer return ans;}// Driver Codepublic static void main(String[] args){ int input[] = {5}; for(int x : input) { System.out.print("sum of all perfect " + "square divisors from " + "1 to " + x + " is: "); // Here we are adding x // because we have not // counted 1 as perfect // squares so if u want to // add it you can just add // that number to the ans System.out.print(x + sums(x) + "\n"); }}}// This code is contributed by Amit Katiyar |
Python3
# Python3 program to find the # sum of all perfect square # divisors of numbers from 1 to N from math import *MOD = 1000000007# Function for finding inverse # of a number iteratively # Here we will find the inverse # of 6, since it appears as # denominator in the formula of # sum of squares from 1 to N def inv (a): o = 1 p = MOD - 2 while (p > 0): if (p % 2 == 1): o = (o * a) % MOD a = (a * a) % MOD p >>= 1 return o # Store the value of the inverse # of 6 once as we don't need to call # the function again and again inv6 = inv(6)# Formula for finding the sum # of first n squaresdef sumOfSquares (n): n %= MOD return (((n * (n + 1)) % MOD * (2 * n + 1)) % MOD * inv6) % MODdef sums (n): # No perfect square exists which # is less than 4 if (n < 4): return 0 # Starting from 2, present value # of start is denoted here as curStart curStart = 2 ans = 0 sqrtN = int(sqrt(n)) while (curStart <= n // curStart): V = n // (curStart * curStart) # Finding end of the segment for # which the contribution will be same end = int(sqrt(n // V)) # Using the above mentioned # formula to find ans % MOD ans += ((n // (curStart * curStart) % MOD * (sumOfSquares(end) + MOD - sumOfSquares(curStart - 1))) % MOD) if (ans >= MOD): ans -= MOD # Now for the next iteration # start will become end+1 curStart = end + 1 # Finally return the answer return ans # Driver Codeif __name__ == '__main__': Input = [5] for x in Input: print("sum of all perfect "\ "square " , end = '') print("divisors from 1 to", x, "is: ", end = '') # Here we are adding x because we have # not counted 1 as perfect squares so if u # want to add it you can just add that # number to the ans print(x + sums(x))# This code is contributed by himanshu77 |
C#
// C# program to find the// sum of all perfect square// divisors of numbers from 1 to Nusing System;class GFG{static readonly int MOD = 7;// Function for finding inverse// of a number iteratively// Here we will find the inverse// of 6, since it appears as// denominator in the formula of// sum of squares from 1 to Nstatic int inv(int a){ int o = 1; for(int p = MOD - 2; p > 0; p >>= 1) { if ((p & 1) == 1) o = (o * a) % MOD; a = (a * a) % MOD; } return o;}// Store the value of the inverse// of 6 once as we don't need to call// the function again and againstatic int inv6 = inv(6);// Formula for finding the sum// of first n squaresstatic int sumOfSquares(int n){ n %= MOD; return (((n * (n + 1)) % MOD * (2 * n + 1)) % MOD * inv6) % MOD;}static int sums(int n){ // No perfect square // exists which is // less than 4 if (n < 4) return 0; // Starting from 2, present // value of start is denoted // here as curStart int curStart = 2, ans = 0; int sqrtN = (int)Math.Sqrt(n); while (curStart <= n / curStart) { int V = n / (curStart * curStart); // Finding end of the segment // for which the contribution // will be same int end = (int)Math.Sqrt(n / V); // Using the above mentioned // formula to find ans % MOD ans += (n / (curStart * curStart) % MOD * (sumOfSquares(end) + MOD - sumOfSquares(curStart - 1))) % MOD; if (ans >= MOD) ans -= MOD; // Now for the next iteration // start will become end+1 curStart = end + 1; } // Finally returning // the answer return ans;}// Driver Codepublic static void Main(String[] args){ int []input = {5}; foreach(int x in input) { Console.Write("sum of all perfect " + "square divisors from " + "1 to " + x + " is: "); // Here we are adding x // because we have not // counted 1 as perfect // squares so if u want to // add it you can just add // that number to the ans Console.Write(x + sums(x) + "\n"); }}}// This code is contributed by Rajput-Ji |
Javascript
<script>// Javascript program to find the// sum of all perfect square// divisors of numbers from 1 to Nlet MOD = 7;// Function for finding inverse// of a number iteratively// Here we will find the inverse// of 6, since it appears as// denominator in the formula of// sum of squares from 1 to Nfunction inv(a) { let o = 1; for (let p = MOD - 2; p > 0; p >>= 1) { if ((p & 1) == 1) o = (o * a) % MOD; a = (a * a) % MOD; } return o;}// Store the value of the inverse// of 6 once as we don't need to call// the function again and againlet inv6 = inv(6);// Formula for finding the sum// of first n squaresfunction sumOfSquares(n) { n %= MOD; return (((n * (n + 1)) % MOD * (2 * n + 1)) % MOD * inv6) % MOD;}function sums(n) { // No perfect square // exists which is // less than 4 if (n < 4) return 0; // Starting from 2, present value // of start is denoted here as // curStart let curStart = 2, ans = 0; let sqrtN = Math.floor(Math.sqrt(n)); while (curStart <= Math.floor(n / curStart)) { let V = Math.floor(n / (curStart * curStart)); // Finding end of the segment // for which the contribution // will be same let end = Math.floor(Math.sqrt(n / V)); // Using the above mentioned // formula to find ans % MOD ans += (Math.floor(n / (curStart * curStart)) % MOD * (sumOfSquares(end) + MOD - sumOfSquares(curStart - 1))) % MOD; if (ans >= MOD) ans -= MOD; // Now for the next iteration // start will become end+1 curStart = end + 1; } // Finally returning the answer return ans;}// Driver Codelet input = [5];for (let x of input) { document.write("sum of all perfect " + "square divisors from " + "1 to " + x + " is: "); // Here we are adding x // because we have not // counted 1 as perfect // squares so if u want to // add it you can just add // that number to the ans document.write(x + sums(x) + "<br>");}// This code is contributed by Saurabh Jaiswal</script> |
Output:
sum of all perfect square divisors from 1 to 5 is: 9
Time Complexity: O(N1/3)
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!