C++ Practice [GESP2506 Level 6] Maximum Factor

GESP Level 6 practice, problem of the lowest common ancestor in a binary tree, difficultyGeneral/Advanced−.

• CCF-GESP C++ Assessment Standards

  Hong Yang, WeChat public account: Hong Yang’s Programming Class CCF-GESP C++ Assessment Standards

Comprehensive Guide – [GESP2506 Level 6] Maximum Factor

Problem Requirements

Problem Description

Given a rooted tree with 10^9 nodes, these nodes are numbered sequentially from 1 to 10^9, with the root node numbered as 1.

For a node numbered k (2 ≤ k ≤ 10^9), its parent node is the largest factor of k excluding k itself.

Now there are q groups of queries, for the i-th (1 ≤ i ≤ q) group of queries given x_i, y_i, please find the distance between the two nodes numbered x_i and y_i in this tree.

The distance between two nodes is the number of edges in the simple path connecting these two nodes.

Input Format

The first line contains a positive integer q, indicating the number of query groups.

Next, q lines, each containing two positive integers x_i, y_i, indicating the node numbers for the queries.

Output Format

Output q lines, each containing an integer representing the distance between nodes x_i and y_i.

Input and Output Examples

Input #1

3

1 3

2 5

4 8

Output #1

1

2

1

Input #2

1

120 650

Output #2

9

Data Range

For 60% of the test cases, guarantee 1 ≤ x_i, y_i ≤ 1000. For all test cases, guarantee 1 ≤ q ≤ 1000, 1 ≤ x_i, y_i ≤ 10^9.

Problem Analysis

Solution Approach

To find the distance between two nodes in a tree constructed under specific rules:

Tree Construction Rules:

• The root node is numbered 1

• For a node k (k≥2), its parent node is the largest proper factor of k (i.e., k divided by the smallest prime factor of k)

• Equivalent statement: Parent node = k / smallest prime factor of k

Solution Approach:

1. <span>get_fa</span> function: Find the parent node of x

• By finding the smallest prime factor i of k (starting from 2)

• If found, the parent node is k/i

• If not found (k is prime), the parent node is 1

<span>get_dis</span> function: Calculate the distance between nodes x and y

• If x=y, the distance is 0

• Otherwise, keep moving the larger node up to its parent until they meet

• Each jump increases the distance by 1

Core Algorithm: Similar to the naive method of finding the lowest common ancestor in a binary tree, but here the two nodes alternate moving up until they meet.

Complexity Analysis:

• Time complexity is O(q·d·√N), where q is the number of queries, d is the height of the tree, and N is the maximum node number (10^9)

• Space complexity is O(1)

Example Code

#include <bits/stdc++.h>using namespace std;int q,x,y;// Get the parent node number of node xint get_fa(int x){    int ans=0;    // Find the smallest prime factor of x    for(int i=2;i<=x/i;i++){        if(x%i==0){            ans=i;  // Found the smallest prime factor            break;        }    }    // If no prime factor found (x is prime), parent node is 1; otherwise parent node is x/smallest prime factor    if(ans==0) ans=1;    else ans=x/ans;    return ans;}// Calculate the distance between nodes x and yint get_dis(int x,int y){    if(x==y) return 0;  // Same node, distance is 0        if(x>y) swap(x,y);  // Ensure y is the larger node        int ans=0;  // Distance counter    while(x!=y){        if(x>y)             x=get_fa(x);  // x is larger, move x up        else             y=get_fa(y);  // y is larger, move y up        ans++;  // Each jump increases distance by 1    }    return ans;}int main(){    scanf("%d",&q);    while(q--){        scanf("%d%d",&x,&y);        printf("%d\n",get_dis(x,y));    }    return 0;}

“Comprehensive Guide–” series problems can be evaluated online atInformatics Olympiad Comprehensive Guide (C++ version).