# COUNTN - Editorial

Author: prathamshalya
Tester: tabr
Editorialist: iceknight1093

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

\mathcal{O}\left(\left\lfloor \frac{M}{2} \right\rfloor + \left\lfloor \frac{M}{3} \right\rfloor + \left\lfloor \frac{M}{5} \right\rfloor + \left\lfloor \frac{M}{7} \right\rfloor + \left\lfloor \frac{M}{11} \right\rfloor + \ldots \right)

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

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])

2 Likes

include <bits/stdc++.h>
using namespace std;

define ll long long

ll pre[1000006];

int main() {

  for(ll i=1;i<1000005;i++){
for(ll j=i+i;j<=1000005;j+=i){
pre[j]=max(pre[j],i);
}
}

// for(int i=1;i<100;i++)
// cout<<i<<" "<<pre[i]<<"\n";

pre[1]=0;

ll ans[1000005];
for(int i=1;i<=1000005;i++)
ans[pre[i]]+=i;

int tc;
cin>>tc;
while(tc--){
int k;
cin>>k;
cout<<ans[k]<<endl;
}


}

Counldn’t understand why my solution doesn’t work if anyone please explain . Thanks in advanced

because your precomputation takes ~1e12 operations which will almost never finish in under the time constraints

static ArrayList seive(int n){
int prime=new int[n+1];
prime[0]=prime[1]=1;
for(int i=2;i<=n;i++)if(prime[i] == 0)
for(int j=i*i;j<=n && j>-1;j+=i)
prime[j]=1;
ArrayList al = new ArrayList<>();
for(int i=2;i<=n;i++) if(prime[i] == 0) al.add(i);
return al;
}

// Just a seive to collect primes

public static void main(String[] args)throws IOException {

ArrayList<Integer> pp = seive(1000000+61);
Collections.sort(pp);

int t=sc.nextInt();
while (t-- > 0){
int k=sc.nextInt();
long ans = 0;

for(int x : pp){
ans += x;
if(k % x == 0) break;
}

System.out.println(ans * k);
}
}


Can anybody help me with case where I am failing, I cant find any as such error or edge case where it is failing still getting WA at Task #2.

Also I am using the same concept of picking prime numbers which are <= min_prime_divisor of K ( I am breaking on the condition when the first smallest prime divides K )

I am sure problem is not related to time limit exceeded and he is getting wrong answer on test case 2 so please can you consider it and see what might be wrong with this solution

Well I found this just now , actually my seive outer loop is running till n and in inner loop i am using int j = i*i ( where i can be >1e5, causing overflow ) and hence WA. I should have used sqrt(n) , but …

Hey bro can you please see what problem might be in anurag92017 's solution he has given above I also happened to have the same problem

Hi @iceknight1093 ,
Solutions with Quadratic time complexity have also passed during the contest. Example submission. Maybe, T could’ve been set to 10^5 or 2 \cdot 10^5. Anyways, since it’s Starters we can allow sub-optimal solutions to pass.

This is just fine with Time complexity maybe you are missing on the numbers N which are > 1e6 . what I mean to say is that you are handling numbers only till n=1e6, but consider the case where for some K ( which is high enough ) and there exists some N greater than 1e6 which you are missing out using this algo .

Try working on that

If I uncomment the line numbers from 50 to 53, it is giving TLE. Otherwise it is getting accepted.
I do not understand why it is happening.
Someone help…

#include <bits/stdc++.h>
using namespace std;

#define int long long
#define el cout << "\n";
#define vi vector<int>

vector<bool> sieve(1e6 + 1, 1); // assign it as global variable
void create_Sieve()
{
sieve[0] = false, sieve[1] = false;
for (int i = 2; i * i <= 1e6; i++)
{
if (sieve[i] == true)
for (int j = i * i; j <= 1e6; j += i)
{
sieve[j] = false;
}
}
}

signed main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int T;
cin >> T;

create_Sieve();
vi prime;
for (int i = 0; i < sieve.size(); i++)
{
if (sieve[i])
{
prime.push_back(i);
}
}

for (int Q = 0; Q < T; Q++)
{
int k;
cin >> k;

int ans = 0;
if (sieve[k])
{
for (int j = 0; (j < prime.size()) && (prime[j] <= k); j++)
{
ans += prime[j];
// if (!(k % prime[j]))
// {
//     break;
// }
}
}
else
{
for (int j = 0; (j < prime.size()) && (prime[j] <= k); j++)
{
ans += prime[j];
if (!(k % prime[j]))
{
break;
}
}
}
cout << ans * k << "\n";
}
return 0;
}



Yeah , that was the case which clicked me after taking a long sleep . Thanks for explaining

HELP ME OUT

import math

import bisect

import collections

from collections import defaultdict, Counter
inf = float(‘inf’)

mod = 10**9 + 7

t = int(input())

maxn = 10**6 + 1

for _ in range(t):

k = int(input())

if k % 2 == 0:
print(k * 2)
continue

def sieve(num):
prime = [True for i in range(num + 1)]
# spf = [i for i in range(num + 1)]
prime[0] = prime[1] = False
for p in range(2, int(num**0.5) + 1):
if prime[p]:
for i in range(p * p, num + 1, p):
prime[i] = False
# if spf[i] == i:
#     spf[i] = p
# return prime, spf
return prime

def smallest(k):
for i in range(2, int(k**0.5)+1):
if k % i == 0:
return i
return k

# prime, spf = sieve(maxn)
prime= sieve(maxn)
s = 0
x = smallest(k)
primevals = []
presum = []
for i in range(len(prime)):
if prime[i]:
s += i
presum.append(s)
print(k * presum[x])


hi can anyone explain why my code is facing tle issues i have tried over dozen submissions trying to optimize here and there but it hasnt got accepted. Please help!!!

Hey I tried this question again after 1 month almost still it is not getting submitted Please somebody help. @anurag92017 @algo_phoenix @manas_rai anyone pls .

from bisect import *
from collections import *
from heapq import *
from types import *

def mi(type): return map(type, input().split())
def li(type): return list(mi(type))

N = 10**6+1
lpf = [0]* N
def sieve(N):
for i in range(2,N):
if lpf[i] :
continue
for j in range(i,N,i):
lpf[j]=i
sieve(N)

prime_prefix_sum = [0]*(N)
def prime_sum(N,arr):
crr_sum = 0
for num in range(2,N):
if lpf[num] == num : # num is prime
crr_sum += num
arr[num] = crr_sum
return arr

prime_prefix_sum = prime_sum(N,prime_prefix_sum)

def solve(k):
if k % 2 == 0:
return k * 2
else:
lowest_prime_factor = lpf[k]
return prime_prefix_sum[lowest_prime_factor]*k

for _ in range(int(input())):
k = int(input())
print(solve(k))