程序员基德

09-21 21:04 中国科学技术大学 C++ 发布于浙江

关注

【秋招笔试】2025.09.21蚂蚁秋招笔试真题改编

✅ 秋招备战指南 ✅

💡 学习建议：

先尝试独立解题
对照解析查漏补缺

🧸 题面描述背景等均已深度改编，做法和题目本质基本保持一致。

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

🌸 目前本专栏已经上线180+套真题改编解析，后续会持续更新的

春秋招笔试机考招合集 -> 互联网必备刷题宝典🔗

蚂蚁

题目一：神秘宝石的组合艺术

1️⃣：分析数字的奇偶性，利用合数的性质

2️⃣：使用Miller-Rabin质数检测算法优化判断

3️⃣：贪心策略选择最少宝石数量

难度：中等

这道题目考查数论知识和贪心算法。关键在于理解合数的定义，并通过数学分析发现最优解的规律。通过分奇偶讨论和质数检测，可以在O(log n)时间内找到最优方案。

题目二：小兰的智能分类系统

1️⃣：理解支持向量机的拉格朗日对偶问题

2️⃣：使用sklearn库求解硬间隔线性SVM

3️⃣：提取并格式化拉格朗日乘数

难度：中等

这道题目结合了机器学习理论和实际编程实现。需要理解SVM的数学原理，特别是拉格朗日对偶问题的求解过程。通过使用成熟的机器学习库，可以高效地获得问题的解。

题目三：小基的高效任务调度系统

1️⃣：理解"高效工作组"的数学条件

2️⃣：使用贪心策略从左到右划分工作组

3️⃣：动态维护最大公约数和组大小

难度：中等偏难

这道题目考查贪心算法和数论中的最大公约数计算。关键insight是一旦满足条件就立即划分，这样能够最大化工作组数量。需要熟练掌握gcd计算和贪心正确性的证明。

01. 神秘宝石的组合艺术

问题描述

小毛是一位古董收藏家，他最近发现了一个古老的宝石组合游戏。游戏规则如下：给定一个目标数值 $n$ ，小毛需要用最少数量的宝石来达到这个数值。

宝石分为两种类型：

基础宝石：每颗价值为 $1$
复合宝石：价值为大于 $1$ 的合数（即除了 $1$ 和自身外还有其他因子的正整数，如 $4, 6, 8, 9, 10, 12, ...$ ）

小毛需要选择至少 $2$ 颗宝石，使得所选宝石的总价值恰好等于 $n$ 。为了展示自己的收藏品味，小毛希望使用的宝石数量尽可能少。如果存在多种最优方案，输出任意一种即可。

输入格式

每个测试文件包含多组测试数据。第一行输入一个整数 $T$ （ $1 \leq T \leq 10^3$ ），表示测试数据组数。

接下来 $T$ 行，每行包含一个正整数 $n$ （ $2 \leq n \leq 10^{18}$ ），表示目标数值。

输出格式

对于每组测试数据：

第一行输出一个正整数 $k$ ，表示选择的宝石数量
第二行输出 $k$ 个整数，表示每颗宝石的价值

如果存在多个最优解，输出任意一个即可。

样例输入

样例输出

数据范围

$1 \leq T \leq 10^3$
$2 \leq n \leq 10^{18}$

样例	解释说明
样例1	目标值8可以用两个价值为4的复合宝石达成，这是最少的宝石数量
样例2	目标值10可以用一个基础宝石(价值1)和一个复合宝石(价值9)达成
样例3	目标值2只能用两个基础宝石达成

题解

这道题的关键在于理解合数的概念和寻找最优策略。

首先分析一下可能的情况：由于我们只能使用价值为1的基础宝石和合数价值的复合宝石，且需要至少2颗宝石，我们可以按照目标值n的奇偶性来分类讨论。

核心观察：答案最多不会超过4颗宝石。

情况分析：

当 n 为奇数且 n ≥ 3 时：
- n-1 是偶数且 ≥ 2，而大于2的偶数都是合数
- 因此可以用1个基础宝石(价值1) + 1个复合宝石(价值n-1)来达成
- 特例：n = 3时，由于3-1 = 2是质数不是合数，只能用3个基础宝石
当 n 为偶数时：
- 首先检查 n-1 是否为合数，如果是，则用1个基础宝石 + 1个复合宝石(价值n-1)
- 如果 n-1 是质数，则考虑用2个基础宝石 + 1个复合宝石(价值n-2)
- 特例：n = 4时，由于4-2 = 2是质数，只能用4个基础宝石
- 特例：n = 2时，只能用2个基础宝石

算法实现：

使用Miller-Rabin算法进行快速质数测试
时间复杂度为 O(log n)

这个贪心策略是正确的，因为我们总是优先选择宝石数量最少的方案，而通过数学分析可以证明上述分类已经涵盖了所有最优情况。

参考代码

Python

import sys
input = lambda:sys.stdin.readline().strip()

def mod_pow(a, d, n):
    """快速幂取模"""
    result = 1
    while d > 0:
        if d & 1:
            result = (result * a) % n
        a = (a * a) % n
        d >>= 1
    return result

def miller_rabin(n):
    """Miller-Rabin质数检测"""
    if n < 2:
        return False
    if n in [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]:
        return True
    if n % 2 == 0:
        return False
    
    # 将n-1表示为d*2^s的形式
    d = n - 1
    s = 0
    while d % 2 == 0:
        d //= 2
        s += 1
    
    # 测试几个底数
    witnesses = [2, 325, 9375, 28178, 450775, 9780504, 1795265022]
    for a in witnesses:
        if a >= n:
            continue
        x = mod_pow(a, d, n)
        if x == 1 or x == n - 1:
            continue
        
        composite = True
        for _ in range(s - 1):
            x = (x * x) % n
            if x == n - 1:
                composite = False
                break
        
        if composite:
            return False
    
    return True

def solve():
    t = int(input())
    for _ in range(t):
        n = int(input())
        gems = []
        
        if n == 2:
            gems = [1, 1]
        elif n == 3:
            gems = [1, 1, 1]
        elif n % 2 == 1:  # 奇数且≥5
            gems = [1, n - 1]
        else:  # 偶数
            x = n - 1
            if x > 1 and not miller_rabin(x):  # x是合数
                gems = [1, x]
            else:
                if n == 4:
                    gems = [1, 1, 1, 1]
                else:
                    gems = [1, 1, n - 2]
        
        print(len(gems))
        print(*gems)

solve()

#include <bits/stdc++.h>
using namespace std;

typedef unsigned long long ull;
typedef __int128 lll;

// 快速幂取模
ull power(ull base, ull exp, ull mod) {
    ull res = 1;
    while (exp > 0) {
        if (exp & 1) res = (lll)res * base % mod;
        base = (lll)base * base % mod;
        exp >>= 1;
    }
    return res;
}

// Miller-Rabin质数测试
bool isPrime(ull n) {
    if (n < 2) return false;
    if (n == 2 || n == 3) return true;
    if (n % 2 == 0) return false;
    
    ull d = n - 1, r = 0;
    while (d % 2 == 0) {
        d /= 2;
        r++;
    }
    
    // 测试底数
    vector<ull> bases = {2, 325, 9375, 28178, 450775, 9780504, 1795265022};
    for (ull a : bases) {
        if (a >= n) continue;
        ull x = power(a, d, n);
        if (x == 1 || x == n - 1) continue;
        
        bool comp = true;
        for (ull i = 0; i < r - 1; i++) {
            x = (lll)x * x % n;
            if (x == n - 1) {
                comp = false;
                break;
            }
        }
        if (comp) return false;
    }
    return true;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int t;
    cin >> t;
    while (t--) {
        ull n;
        cin >> n;
        vector<ull> ans;
        
        if (n == 2) {
            ans = {1, 1};
        } else if (n == 3) {
            ans = {1, 1, 1};
        } else if (n % 2 == 1) {  // 奇数且≥5
            ans = {1, n - 1};
        } else {  // 偶数
            ull val = n - 1;
            if (val > 1 && !isPrime(val)) {  // val是合数
                ans = {1, val};
            } else {
                if (n == 4) {
                    ans = {1, 1, 1, 1};
                } else {
                    ans = {1, 1, n - 2};
                }
            }
        }
        
        cout << ans.size() << "\n";
        for (int i = 0; i < ans.size(); i++) {
            if (i > 0) cout << " ";
            cout << ans[i];
        }
        cout << "\n";
    }
    
    return 0;
}

Java

import java.util.*;
import java.io.*;

public class Main {
    
    // 快速幂取模
    public static long modPow(long base, long exp, long mod) {
        long result = 1;
        while (exp > 0) {
            if ((exp & 1) == 1) {
                result = multiplyMod(result, base, mod);
            }
            base = multiplyMod(base, base, mod);
            exp >>= 1;
        }
        return result;
    }
    
    // 防止乘法溢出的模乘
    public static long multiplyMod(long a, long b, long mod) {
        return ((a % mod) * (b % mod)) % mod;
    }
    
    // Miller-Rabin质数测试
    public static boolean isPrime(long n) {
        if (n < 2) return false;
        if (n == 2 || n == 3) return true;
        if (n % 2 == 0) return false;
        
        long d = n - 1, r = 0;
        while (d % 2 == 0) {
            d /= 2;
            r++;
        }
        
        // 测试底数
        long[] bases = {2, 325, 9375, 28178, 450775, 9780504L, 1795265022L};
        for (long a : bases) {
            if (a >= n) continue;
            long x = modPow(a, d, n);
            if (x == 1 || x == n - 1) continue;
            
            boolean composite = true;
            for (long i = 0; i < r - 1; i++) {
                x = multiplyMod(x, x, n);
                if (x == n - 1) {
                    composite = false;
                    break;
                }
            }
            if (composite) return false;
        }
        return true;
    }
    
    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int t = Integer.parseInt(br.readLine());
        
        while (t-- > 0) {
            long n = Long.parseLong(br.readLine());
            List<Long> result = new ArrayList<>();
            
            if (n == 2) {
                result.add(1L);
                result.add(1L);
            } else if (n == 3) {
                result.add(1L);
                result.add(1L);
                result.add(1L);
            } else if (n % 2 == 1) {  // 奇数且≥5
                result.add(1L);
                result.add(n - 1);
            } else {  // 偶数
                long val = n - 1;
                if (val > 1 && !isPrime(val)) {  // val是合数
                    result.add(1L);
                    result.add(val);
                } else {
                    if (n == 4) {
                        result.add(1L);
                        result.add(1L);
                        result.add(1L);
                        result.add(1L);
                    } else {
                        result.add(1L);
                        result.add(1L);
                        result.add(n - 2);
                    }
                }
            }
            
            System.out.println(result.size());
            for (int i = 0; i < result.size(); i++) {
                if (i > 0) System.out.print(" ");
                System.out.print(result.get(i));
            }
            System.out.println();
        }
    }
}