PROBLEM LINK:
Practice
Contest: Division 1
Contest: Division 2
Contest: Division 3
Contest: Division 4
Author: prathamshalya
Tester: tabr
Editorialist: iceknight1093
DIFFICULTY:
TBD
PREREQUISITES:
Sieve of Eratosthenes, prefix sums
PROBLEM:
Let f(N) denote the largest factor of N that is not N itself. f(1) = 0.
You’re given K. Find the sum of all N such that f(N) = K.
EXPLANATION:
First, observe that f(N) = \frac{N}{p}, where p is the smallest prime factor of N.
So, if we want f(N) = K, we must have N = K\cdot p, where p should be the smallest prime factor of N.
Clearly, choosing different values of p will give us different values of p, so we can instead focus on which p can possibly be chosen.
Since N = K\cdot p, every prime factor of N will also be a prime factor of K; except possibly p itself.
In particular, let q denote the smallest prime factor of K.
Then,
- If p \gt q, p will definitely not be the smallest prime factor of N since q will also divide it.
- If p \leq q, p will definitely be the smallest prime factor of N.
So, the only valid integers N are those of the form K\cdot p, where p is a prime that doesn’t exceed q.
We’re now left with two tasks: finding q quickly, and then computing the answer.
One way to find q is to simply precompute it for every integer between 1 and 10^6 before answering the test cases.
Let \text{spf}[n] denote the smallest prime factor of n. Initially, set this to 0 for every n.
Then, do the following:
- Iterate over integers p from 2 to 10^6.
- If \text{spf}[p] = 0 then p is a prime, otherwise it isn’t.
- If p is a prime, iterate over all its multiples.
For each multiple x, if \text{spf}[x] = 0, set \text{spf}[x] = p.
At the end of this process, the \text{spf} array will hold the values we want.
The complexity of this is \mathcal{O}(M\log\log M), where M = 10^6.
This is because the complexity of the algorithm is
and the sum of the reciprocals of the primes exhibits log-log growth.
Once q is known, we want to compute the sum of K\cdot p across all primes p \leq q.
Note that this is just K multiplied by the sum of all primes that don’t exceed q.
Our earlier sieve also told us which integers are primes, and so the sum of all primes not exceeding q can be computed from there using a simple prefix sum.
TIME COMPLEXITY:
\mathcal{O}(1) per testcase after \mathcal{O}(M\log \log M) precomputation, where M = 10^6.
CODE:
Author's code (C++)
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF (int)1e18
mt19937_64 RNG(chrono::steady_clock::now().time_since_epoch().count());
const int N = 1e6 + 69;
int sp[N];
int p[N];
void Solve()
{
int n; cin >> n;
int x = sp[n];
int ans = p[x];
ans *= n;
assert(n != 1);
cout << ans << "\n";
}
int32_t main()
{
auto begin = std::chrono::high_resolution_clock::now();
ios_base::sync_with_stdio(0);
cin.tie(0);
int t = 1;
// freopen("in", "r", stdin);
// freopen("out", "w", stdout);
for (int i = 2; i < N; i++){
if (sp[i] == 0){
p[i] = i;
}
p[i] += p[i - 1];
for (int j = i; j < N; j += i){
if (sp[j] == 0) sp[j] = i;
}
}
cin >> t;
for(int i = 1; i <= t; i++)
{
//cout << "Case #" << i << ": ";
Solve();
}
auto end = std::chrono::high_resolution_clock::now();
auto elapsed = std::chrono::duration_cast<std::chrono::nanoseconds>(end - begin);
cerr << "Time measured: " << elapsed.count() * 1e-9 << " seconds.\n";
return 0;
}
Editorialist's code (Python)
maxn = 10**6
spf = [0]*maxn
pref = [0]*maxn
for i in range(2, maxn):
pref[i] = pref[i-1]
if spf[i] == 0:
pref[i] += i
for j in range(i, maxn, i):
if spf[j] == 0: spf[j] = i
for _ in range(int(input())):
k = int(input())
p = spf[k]
print(k * pref[p])