COUNTN - Editorial

editorial
, , ,
1

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

\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

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

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

define ll long long

ll pre[1000006];

int main() {
// your code goes here

  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

3

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

4

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 )

5

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

6

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 …

8

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

9

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.

11

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

12

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;
}
13

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

14

HELP ME OUT :slight_smile:

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!!!

15

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

def input(): return sys.stdin.readline().rstrip()
def mi(type): return map(type, input().split())
def li(type): return list(mi(type))

N = 10**7 + 10
lpf = [0] * N

def sieve(N):
for i in range(2, N):
if lpf[i] > 0: continue
for j in range(i, N, i):
if lpf[j] == 0: # so that to stores the minimum prime factor of a num
lpf[j] = i
sieve(N)

def solve(k):
if k % 2 == 0:
return k * 2
else:
ans = k * 2
if lpf[k] == k : # i.e k is prime
for num in range(3,k+1,2):
if lpf[num] == num : # i.e num is prime finding all the primes <= k
ans += num*k
else:
for i in range(3,k+1, 2):
num = i * k
if num//lpf[num] == k :
ans += num
else: # we found a i for which i * other factor of num > k
break
return ans

for _ in range(int(input())):
k = int(input())
print(solve(k))
hey can anyone tell why this code is failing for even case it’s obvious and then for odd case i have divided into 2 parts

  1. when then k is prime then we will take all the prime less than k as factor .
  2. when k is not a prime