阿里7.20机考题

1. 给定N和K，求互不相同的正整数x,y,z使得x+y+z=N，且gcd(x,y)=gcd(x,z)=gcd(y,z)=K。

条件：1 ≤N, K≤ 1e18

思路：等式两边除K，得到x'+y'+z'=N'=N/K，且x',y',z'两两互素。

当N'为偶数，直接构造x'=1, y'=N'/2, z' = y'-1满足条件。

当N'为奇数，另x'=1,则y'+z'=N'-1。由于N'-1为偶数且y'和z'互素，必然有y',z'都为奇数。令y'=3,5,..., N' / 2逐个搜索即可。

在这里讨论一下N'为奇数时搜索的复杂度。

考虑奇素数pi，如果y'=p_i不满足条件，那么必然有z'与p_i不互素，也就是p_i整除z'，从而p_i整除p_i+z'=N'-1

考虑y'为前15个奇素数p₁,...,p₁₅。如果均不满足条件，那么他们的乘积p₁p₂...p₁₅也整除N'-1。考虑到前15个奇素数的积已经超过了1e18，矛盾。

因此我们搜索到第15个奇素数（53）的时候一定能找到一对满足条件的y'和z'。因此搜索复杂度为O(p₁₅)=O(1)。

using ll = long long;

for (int kase = 1; kase <= T; kase++) {
    cin >> n >> k;
    if (n % k != 0) cout << -1 << endl;
    else {
        n /= k;
        if (n < 6) cout << -1 << endl;
        else if (n % 2 == 0) {
            ll j = (n - 1) / 2;
            cout << k << " " << k * j << " " << k * (j + 1) << endl;
        }
        else {
            bool found = false;
            for (ll p = 3; p < n - 1 - p && !found; p += 2) {
                ll q = n - 1 - p;
                if (__gcd(p, q) == 1) {
                    cout << k << " " << k * p << " " << k * q << endl;
                    found = true;
                }
            }
            if (!found) cout << -1 << endl;
        }
    }
}

2. 求区间[l, r]内的幸运数。幸运数定义为，将相邻数位差的绝对值拼成下一个数，重复该操作直到只剩1位。剩下7的是幸运数。例如，219->18->7或者118->7

条件：1 ≤ l ≤ r ≤ 1e9

思路：根据1,...,k-1位的幸运数，给定首位数字，可以搜索得到k位的幸运数。将所有幸运数排序后进行二分查找。

因为每一个更长的幸运数都可以通过题目里规定的操作变成一个更短的幸运数，反过来讲，给定每个幸运数的首位 for i in {1, ..., 9}，它都可以通过一个比他短的幸运数计算得到。

比如给定首位是1,可以算 7->18。根据18，给定首位是2，又可以算出18->219。

不断这样以小算大，可以算出所有幸运数。

注意k位的幸运数不仅可以通过k-1的幸运数计算得到，还可以通过更短的幸运数在前方补0到k-1位后计算得到。例如：7补成007，可以计算得到1118,2229,7770,8881,9992。

void dfs(vector<pair<int, vector<int>>> mem[], vector<int>& ref, int digits, int cur, int idx) {
    if (idx == digits) {
        vector<int> dcur;
        for (int c = cur; c; c /= 10) dcur.push_back(c % 10);
        reverse(dcur.begin(), dcur.end());
        mem[digits].push_back({cur, dcur});
    }
    else if (idx == 0) {
        for (int i = 1; i <= 9; i++)
            dfs(mem, ref, digits, cur * 10 + i, idx + 1);
    }
    else {
        int pos = idx - (digits - (int)ref.size());
        int diff = pos >= 0 ? ref[pos] : 0;
        int last = cur % 10;
        if (diff == 0)
            dfs(mem, ref, digits, cur * 10 + last, idx + 1);
        else {
            for (int sign : {-1, 1}) {
                int val = last + diff * sign;
                if (val < 0 || val > 9) continue;
                else dfs(mem, ref, digits, cur * 10 + val, idx + 1);
            }
        }
    }
}

int main() {
    const int maxdigits = 9;
    vector<pair<int, vector<int>>> luckies[maxdigits + 1];

    luckies[1].push_back({7, {7}});
    for (int digits = 2; digits <= maxdigits; digits++)
        for (int i = 1; i <= digits - 1; i++)
            for (auto& ref : luckies[i])
                dfs(luckies, ref.second, digits, 0, 0);

    vector<int> lucky_nums;
    for (int digits = 1; digits <= maxdigits; digits++)
        for (auto& v : luckies[digits])
            lucky_nums.push_back(v.first);
    sort(lucky_nums.begin(), lucky_nums.end());

    int T, l ,r;
    cin >> T;
    for (int ks = 1; ks <= T; ks++) {
        cin >> l >> r;
        auto pr = upper_bound(lucky_nums.begin(), lucky_nums.end(), r);
        auto pl = upper_bound(lucky_nums.begin(), lucky_nums.end(), l - 1);
        cout << pr - pl << endl;
    }
    return 0;
}

#笔试题目#