【秋招笔试】09.26阿里云秋招(已改编)-三语言题解

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

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

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

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

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

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

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

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

alt

🌈 阿里云秋招笔试,来啦!!!

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

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));
                }
            }
   

剩余60%内容,订阅专栏后可继续查看/也可单篇购买

本专栏短期内不再更新,请勿继续订阅

全部评论

相关推荐

咦哟,从去年八月份开始长跑,两处实习转正都失败了,风雨飘摇,终于拿到offer了更新一下面试记录:秋招:多部门反复面试然后挂掉然后复活,具体问了啥已经忘了,只是被反复煎炸,直至焦香😋春招:base北京抖音hr打来电话说再次复活,准备面试,gogogo北京抖音一面:六道笔试题:1.promise顺序2.定义域问题3.flat展开4.并发请求5.岛屿数量算法(力扣)深度,广度都写6.忘记了,好像也是算法,难度中等其他问题多是框架底层设计,实习项目重难点~~~秒过😇北京抖音二面:三道笔试题:(为什么只有三道是因为第三道没做出来,卡住了)1.中等难度算法(忘记啥题了,应该是个数组的)2.认识js的继承本质(手写继承模式,深入js的面相对象开发)3.手写vue的响应式(卡在了watch,导致挂掉)---后知后觉是我的注册副作用函数写得有问题,有点紧张了其他题目多是项目拷打,项目亮点,对实习项目的贡献~~~第二天,挂,but立马复活转战深圳客服当天约面深圳客服一面:六道笔试题,由于面过太多次字节,面试官叫我直接写,不用讲,快些写完😋,具体都是些继承,深拷贝(注意对数组对象分开处理,深层次对象,循环引用),加中等难度算法题~~~秒过深圳客服二面:口诉八股大战:大概囊括网络,浏览器渲染原理,动画优化,时间循环,任务队列等等(你能想到的简单八股通通拉出来鞭尸😋)算法题:笔试题6道:1:找出数组内重复的数,arr[0]-arr[n]内的数大小为[1-n],例如[1,2,2,3,3]返回[2,3],要求o(n),且不使用任何额外空间(做到了o(n),空间方面欠佳,给面试官说进入下一题,做不来了)2:原滋原味的继承(所以继承真滴很重要)3:力扣股票购买时机难度中等其他滴也忘记了,因为拿到offer后鼠鼠一下子就落地了,脑子自动过滤掉可能会攻击鼠鼠的记忆😷~~~秒过深圳客服三面:项目大战参与战斗的人员有:成员1:表单封装及其底层原理,使用成本的优化,声明式表单成员2:公司内部库生命周期管理成员3:第三方库和内部库冲突如何源码断点调试并打补丁解决成员4:埋点的艺术成员5:线上项目捷报频传如何查出内鬼成员6:大文件分片的风流趣事成员7:设计模式对对碰成员8:我构建hooks应对经理的新增的小需求的故事可能项目回答的比较流利,笔试题3道,都很简单,相信大家应该都可以手拿把掐😇~~~过过过无hr面后续煎熬等待几天直接hr打电话发offer了,希望大家也可以拿到自己心仪的offer
法力无边年:牛哇,你真是准备得充分,我对你没有嫉妒,都是实打实付出
查看19道真题和解析
点赞 评论 收藏
分享
评论
3
9
分享

创作者周榜

更多
牛客网
牛客企业服务