cppAcademy
FROM LEARNING TO COMPETING

Expert.
Put your skills to the test.

Bulgarian Informatics Group A · 2009–2026

217 independently explained problems: 54 Municipal, 54 Regional and 109 National. Start with the easier tasks and work upwards. Difficulty labels are learning estimates, not official ratings; Group A also includes challenging national-level problems. The 109 National-round tasks shared by Groups A and B retain their existing permanent URLs and explanations. Years follow Arena’s competition-season labels. Source clarifications and special grader requirements are noted on affected tasks.
GROUP A2014 · MediumPrime sieve

Table

National Olympiad — Regional round (2014 season)

Submission name: tab.cpp

Solve in Editor →

Problem summary

Fill an N by N table row-major with 1 first, then numbers 2..N² ordered by their number of distinct prime divisors, breaking ties numerically. Find the entry at row r, column c.

Input

N r c.

Output

The requested integer.

Constraints

2 ≤ N ≤ 1000; 1 ≤ r,c ≤ N.

Worked example

Official statement sample.

Input

5 4 2

Output

10

Solution analysis

  1. Compute omega[x], the number of distinct prime divisors of x, by a sieve. Whenever omega[p] is zero at p≥2, p is prime; add one to every multiple of p. Prime powers contribute just one because each prime is processed once.
  2. The desired row-major rank is (r−1)N+c, counting from one. Count how many integers have each omega value and subtract entire groups until the rank falls in one group. Scan x increasingly within that group to obtain the required member.
  3. For N=5 the first group after 1 contains prime powers such as 2,4,8,9,16,25. Row 4 column 2 has rank 17, which is the second number with two distinct prime divisors: 10.

Why it works

The sieve increments x exactly for each distinct prime dividing x, so omega is correct. Ordering groups by omega and scanning each group numerically is exactly the prescribed total order. Rank subtraction and the final scan locate the requested row-major entry.

Complexity: O(N² log log(N²)) time and O(N²) space.

Watch out. Count distinct prime factors, not factors with multiplicity. The number 1 has zero prime divisors and is first.

Commented C++17 solution

An independently written complete program with standard headers.

#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int main(){
    int n,r,c;
    cin>>n>>r>>c;
    int limit=n*n;
    vector<int>omega(limit+1,0);
    // Each prime increments all of its multiples exactly once.
    for(int p=2;p<=limit;++p){
        if(omega[p]==0){
            for(int x=p;x<=limit;x+=p){
                ++omega[x];
            }
        }
    }
    int maximum=*max_element(omega.begin(),omega.end());
    vector<int>count(maximum+1,0);
    for(int x=1;x<=limit;++x){
        ++count[omega[x]];
    }
    int rank=(r-1)*n+c;
    int group=0;
    while(rank>count[group]){
        rank-=count[group++];
    }
    for(int x=1;x<=limit;++x){
        if(omega[x]==group&&--rank==0){
            cout<<x<<'\n';
            break;
        }
    }
}

Source: Arena Olimpiici ↗