2022ICPC 网络赛第二场 F Infinity Tree

You have a rooted tree with infinite number of nodes.

At the beginning, the tree has only one node (numbered 1 and is the root node), and every second, each node will add k child nodes. Specifically, if at the xth second this tree has p nodes, and at (x+1)th second, the number of nodes will become (k+1)×p. For the node numbered y(1≤y≤p), the generated k child nodes are numbered in [p+(y−1)×k+1,p+y×k].

Now you want to know the lowest common ancestors of two nodes x,y.

For two nodes u and v of a rooted tree T, the lowest common ancestors LCA(T,u,v) represents a node x such that x is the ancestor of u and v and the depth of x is as large as possible. Here, a node can also be its own ancestor.

输入格式:

The input consists of multiple test cases.

The first line contains a single integer T(1≤T≤10^5), indicating there are T test cases.

In each test case:

The only line contains three positive integers k,x,y(2≤k,x,y≤10^18), representing the parameters and query nodes of the tree.

输出格式:

For each case,the output contains a single number, indicating the the lowest common ancestors of the query nodes.

输入样例:

3
2 6 7
2 4 5
3 20 2

输出样例:

2
1
2

 题意：

你有一个有无限个结点的根树。开始时，树只有一个节点(编号为1，是根节点)，每秒钟，每个节点将添加k个子节点。如果在第x秒时，树有p个节点，而在第(x+1)秒时，节点的数量将变为(k+1)*p。对于编号为 y (1≤y≤p)的节点，生成的k个子节点编号为 [p+(y−1)*k+1,p+y*k]。

现在你想知道两个节点 x , y 的最小公共祖先结点。

对于根树 T 的两个节点 u 和 v ，最低的公共祖先 LCA(T,u,v)表示一个节点x，使x是u和v的祖先，并且x的深度尽可能大。在这里，节点也可以是它自己的祖先。

结点数：p = (k+1)^n  因为x , y <= 1e18  所以 p <= 1e18  log(k+1)1e18 = n   n  ~= 38 

 long long表示 -2^63到2^63-1

 -9223372036854775808～9223372036854775807  (19位数， 9e18 )

所以外层可能会超出long long，使用__int128 详解__int128 - FReQuenter - 博客园 (cnblogs.com)

 直接模拟 ， 分别找到样例x , y 的祖上直到根

#include 
#include 
#include 
#include 
#include 
 
using namespace std;
typedef  long long ll;
const ll inf = 1e18+10;
int n ;
ll k, x, y;
 
vector vt;
 
void init(){
    vt.clear();
    ll p = 1;
    vt.push_back(1);
// 当p足够大的时候(k+1)*p会超出long long的表示范围，导致无法与inf比较大小 强制转换为__int128
    while( (__int128)(k + 1) * p < inf ){ 
    //while( p < inf/(k + 1) ){ 
        p = (k + 1) * p ;
        vt.push_back(p);
    }
}
 
ll lowerbound(ll a) //二分 找出最大的小于a的数
{
    int l = 0 , r = vt.size()-1;
    while( l < r ) 
    {
        int mid = l + r + 1 >> 1;
        if( vt[mid] < a ) l = mid ;
        else r = mid - 1;
    }
    return vt[l];
}
 
void solve(ll a , queue& q)
{
    while(a != 1){
        q.push(a);
        ll p = lowerbound(a);//找出最大的小于a的数 
        a = (a-p-1)/k + 1;   //找出父节点  向0取整 
    }
    q.push(a);
}
 
int main()
{
    
    ios::sync_with_stdio(false); 
    cin.tie(0); 
    cout.tie(0);
    cin >> n;
    while(n--){
        cin >> k >> x >> y ;
        init();
        queue q1 , q2 ;
        solve(x,q1);
        solve(y,q2);
        while(q1.front() != q2.front()){
            if( q1.front() > q2.front() ) //弹出大值 深入根节点
                q1.pop();
            else q2.pop();
        }
        cout << q1.front() << endl;//相等则为答案
   }
    return 0;
}