In this

**HackerEarth Number of divisors problem solution,**You are given two numbers n and k. For each number in the interval [1, n], your task is to calculate its largest divisor that is not divisible by k. Print the sum of these divisors.## HackerEarth Number of divisors problem solution.

`#include<bits/stdc++.h>`

using namespace std;

using ll = long long;

long long f(int n, int k) {

if (n == 0) return 0;

long long res = (n/k);

return f(n/k, k) + n * (ll)(n+1) / 2ll - (res * (res + 1) / 2ll) * k;

}

int main () {

int T = 1;

scanf("%d", &T);

assert(T >= 1 && T <= 300000);

while(T--) {

int n, k;

scanf("%d%d", &n, &k);

assert(n <= 1e9);

assert(k >= 2 && k <= 1e9);

printf("%lld\n", f(n, k));

}

return 0;

}

## 0 Comments