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