Sum of all perfect square divisors of numbers from 1 to N | C ++ Program to find the sum of all perfect square divisors of numbers from 1 to N ; 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 ; Store the value of the inverse of 6 once as we don 't need to call the function again and again ; Formula for finding the sum of first n squares ; No perfect square exists which is less than 4 ; Starting from 2 , present value of start is denoted here as curStart ; Finding end of the segment for which the contribution will be same ; Using the above mentioned formula to find ans % MOD ; Now for mthe next iteration start will become end + 1 ; Finally returning the answer ; Driver Code ; 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
#include <bits/stdc++.h> NEW_LINE using namespace std ; #define MOD  1000000007 NEW_LINE #define int  unsigned long long NEW_LINE 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 ; } int inv6 = inv ( 6 ) ; int sumOfSquares ( int n ) { n %= MOD ; return ( ( ( n * ( n + 1 ) ) % MOD * ( 2 * n + 1 ) ) % MOD * inv6 ) % MOD ; } int sums ( int n ) { if ( n < 4 ) return 0 ; int curStart = 2 , ans = 0 ; int sqrtN = sqrt ( n ) ; while ( curStart <= n / curStart ) { int V = n / ( curStart * curStart ) ; int end = sqrt ( n / V ) ; ans += ( n / ( curStart * curStart ) % MOD * ( sumOfSquares ( end ) + MOD - sumOfSquares ( curStart - 1 ) ) ) % MOD ; if ( ans >= MOD ) ans -= MOD ; curStart = end + 1 ; } return ans ; } int32_t main ( ) { int input [ ] = { 5 } ; for ( auto x : input ) { cout << " sum ▁ of ▁ all ▁ perfect " << " ▁ square ▁ divisors ▁ from " << " ▁ 1 ▁ to ▁ " << x << " ▁ is : ▁ " ; cout << x + sums ( x ) << endl ; } return 0 ; }