abc044d <根号分治>

标签：tasks return cout LL abc044d include

https://atcoder.jp/contests/abc044/tasks/arc060_b

// https://atcoder.jp/contests/abc044/tasks/arc060_b
// 根号分治
// 将数据范围分为两部分处理, 使得拆开成两部分后各部分复杂度均符合要求

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
typedef long long LL;

LL f(LL b, LL n)
{
    if (n < b) return n;
    else return f(b, n / b) + n % b;
}

void solv()
{
    LL n, s, b;
    cin >> n >> s;
    if (n == s)
    {
        cout << n + 1 << endl;
        return;
    }
    if (n < s)
    {
        cout << -1 << endl;
        return;
    }
    // 尝试 b = 2 ~ sqrt n
    LL n2 = sqrt(n);
    for (b = 2; b <= n2; b ++)
    {
        if (f(b, n) == s)
        {
            cout << b << endl;
            return;
        }
    }
    // 检查 b = sqrt n  ~  n
    // 假设 n = pb + q, s = p + q
    // p(b-1) = n-s
    // 可知 p 的范围为 1 ~ sqrt n, 因而枚举 p进行检查
    // 注意 p 从大到小枚举, 如此得到的b才是从小到大
    for (int p = n2; p > 0; p --)
    {
        if ((n-s) % p == 0)
        {
            b = (n-s) / p + 1;
            if (f(b, n) == s)
            {
                cout << b << endl;
                return;
            }
        }
    }
    cout << -1 << endl;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
    // cin >> T;
    while (T --)
    {
        solv();
    }
    return 0;
}

标签：tasks,return,cout,LL,abc044d,include
From： https://www.cnblogs.com/o2iginal/p/17492994.html