🍭 大家好这里是 春秋招笔试突围，一起备战大厂笔试

💻 ACM金牌团队🏅️ | 多次AK大厂笔试 ｜ 大厂实习经历

✨ 本系列打算持续跟新 春秋招笔试题

👏 感谢大家的订阅➕ 和 喜欢💗 和 手里的小花花🌸

✨ 笔试合集传送们 -> 🧷春秋招笔试合集

🍒 本专栏已收集 100+ 套笔试题，笔试真题 会在第一时间跟新

🍄 题面描述等均已改编，如果和你笔试题看到的题面描述不一样请理解，做法和题目本质基本不变。

🍹 感谢各位朋友们的订阅，你们的支持是我们创作的最大动力 💞

🌈 阿里云秋招笔试，来啦！！！

🍥 本次是标准的阿里系数学场，三道都和数论有关～

1️⃣ 快速幂+推公式，难度不大，简单的等比数列求和

2️⃣ 约数相关，暴力枚举每个数的因子暴力check即可

3️⃣ 质数筛+思维+DFS，这题考查的比较全面，是个非常好的巩固知识点的题目。

✨ 01.魔法装备升级 评测链接🔗

问题描述

在魔法世界中，K小姐是一位著名的魔法装备师。她最近接到了一个特殊的订单：为一群冒险者升级他们的魔法装备。每件装备的初始等级为 1 级，升级过程中需要使用特殊的魔法结晶。

升级规则如下：

• 从 1 级升到 2 级需要 个魔法结晶
• 从 2 级升到 3 级需要 个魔法结晶
• 从 3 级升到 4 级需要 个魔法结晶
• 以此类推，从 级升到 级需要 个魔法结晶

K小姐喜欢一次性准备好所有需要的魔法结晶。现在，她需要你的帮助来计算出总共需要准备多少个魔法结晶。

输入格式

第一行包含两个整数 和 （；），分别表示装备种类数量和魔法结晶的基数。

第二行包含 个整数 （），其中 表示需要升级到 级的装备数量。

输出格式

输出一个整数，表示K小姐需要准备的魔法结晶总数。由于这个数可能非常大，请将结果对 取模后输出。

样例输入

5 2
0 0 1 2 3

样例输出

124

数据范围

• 
• 
• 

题解

推公式+快速幂

这道题目本质上是一个等比数列求和的问题，但需要注意大数运算和取模的处理。

对于每种等级的装备，需要计算从 1 级升级到该等级所需的总魔法结晶数。这实际上是一个等比数列的前 项和：

• 等比数列求和公式为：，其中 是首项， 是公比。在我们的问题中，，。

因此，对于每种等级 的装备，我们需要计算：

关键点：

• 使用快速幂计算
• 使用费马小定理计算模逆元：
• 注意在每一步计算中都要取模，以避免溢出

参考代码

• Python

def quick_pow(base, exp, mod):
    """快速幂函数，用于高效计算大数的幂"""
    result = 1
    while exp > 0:
        if exp & 1:
            result = (result * base) % mod
        base = (base * base) % mod
        exp >>= 1
    return result

# 读取输入
n, t = map(int, input().split())
a = list(map(int, input().split()))

MOD = 998244353
inv = quick_pow(t - 1, MOD - 2, MOD)  # 计算 (t-1) 的模逆元
result = 0

# 遍历每种等级的装备
for i in range(1, n + 1):
    if a[i - 1] == 0:
        continue
    # 计算 t^(i-1) - 1
    temp = (quick_pow(t, i - 1, MOD) - 1 + MOD) % MOD
    # 计算 a[i-1] * t * (t^(i-1) - 1) / (t - 1)
    result += a[i - 1] * t % MOD * temp % MOD * inv % MOD
    result %= MOD

# 输出结果
print(result)

• Java

import java.util.Scanner;

public class Main {
    static final int MOD = 998244353;

    static long quickPow(long base, long exp) {
        long result = 1;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = (result * base) % MOD;
            }
            base = (base * base) % MOD;
            exp >>= 1;
        }
        return result;
    }

    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int n = scanner.nextInt();
        long t = scanner.nextLong();
        long[] a = new long[n];

        for (int i = 0; i < n; i++) {
            a[i] = scanner.nextLong();
        }

        long inv = quickPow(t - 1, MOD - 2);  // 计算 (t-1) 的模逆元
        long result = 0;

        // 遍历每种等级的装备
        for (int i = 1; i <= n; i++) {
            if (a[i - 1] == 0) continue;
            // 计算 t^(i-1) - 1
            long temp = (quickPow(t, i - 1) - 1 + MOD) % MOD;
            // 计算 a[i-1] * t * (t^(i-1) - 1) / (t - 1)
            result += a[i - 1] * t % MOD * temp % MOD * inv % MOD;
            result %= MOD;
        }

        System.out.println(result);
    }
}

• Cpp

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 998244353;

long long quick_pow(long long base, long long exp) {
    long long result = 1;
    while (exp > 0) {
        if (exp & 1) {
            result = (result * base) % MOD;
        }
        base = (base * base) % MOD;
        exp >>= 1;
    }
    return result;
}

int main() {
    int n;
    long long t;
    cin >> n >> t;
    vector<long long> a(n);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    long long inv = quick_pow(t - 1, MOD - 2);  // 计算 (t-1) 的模逆元
    long long result = 0;

    // 遍历每种等级的装备
    for (int i = 1; i <= n; i++) {
        if (a[i - 1] == 0) continue;
        // 计算 t^(i-1) - 1
        long long temp = (quick_pow(t, i - 1) - 1 + MOD) % MOD;
        // 计算 a[i-1] * t * (t^(i-1) - 1) / (t - 1)
        result += a[i - 1] * t % MOD * temp % MOD * inv % MOD;
        result %= MOD;
    }

    cout << result << endl;
    return 0;
}

🌈 02.魔法宝石的最佳搭配 评测链接🔗

问题描述

在魔法世界中，K小姐是一位著名的宝石鉴定师。她最近发现了一种特殊的魔法宝石，其魔力值为 。她想要找到另一种宝石与之搭配，使得它们的魔力效果最大化。

搭配规则如下：

1. 搭配宝石的魔力值 必须小于主宝石的魔力值 ，即 。
2. 两颗宝石的魔力效果计算公式为：，其中 表示 和 的最大公约数。

K小姐希望你能帮她找出能产生最大魔力效果的搭配。

输入格式

第一行输入一个整数 （），表示测试用例的数量。

接下来的 行，每行包含一个正整数 （），表示主宝石的魔力值。

输出格式

对于每个测试用例，输出一行，包含一个整数，表示最大可能的魔力效果值。

样例输入

3
3
6
5

样例输出

5
27
9

数据范围

• 
• 

题解

约数

问题的关键在于正确理解公式 并找到使其最大化的 值。

搜索结果中的代码通过枚举所有可能的 值来找到最大值，这是一种暴力但正确的方法，然而，对于较大的 值，这种方法可能会超时。

可以优化这个算法，只枚举 的因子，因为最优的 一定是 的因子。

但我们要考虑最优情况是

优化后的算法步骤：

1. 枚举 的所有因子。
2. 对每个因子 ，计算 。
3. 返回所有计算结果中的最大值。
4. 注意答案要和 取最大，因为当 时，。

参考代码

• Python

import math

def max_value(x):
    result = 2 * x - 1  # 初始化结果为 2x - 1
    for y in range(1, int(math.sqrt(x)) + 1):
        if x % y == 0:
            # 检查 y
            result = max(result, (x + y) * y)
            # 检查 x // y，如果不等于 y
            if y != x // y and y != 1:
                result = max(result, (x + x // y) * (x // y))
    return result

# 读取测试用例数量
t = int(input())

# 处理每个测试用例
for _ in range(t):
    x = int(input())
    print(max_value(x))

• Java

import java.util.Scanner;

public class Main {
    public static long maxValue(long x) {
        long result = 2 * x - 1;  // 初始化结果为 2x - 1
        for (long y = 1; y * y <= x; y++) {
            if (x % y == 0) {
                // 检查 y
                result = Math.max(result, (x + y) * y);
                // 检查 x / y，如果不等于 y
                if (y != x / y && y != 1) {
                    result = Math.max(result, (x + x / y) * (x / y));
                }
            }