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

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

✨ 笔试合集传送们 -> 🧷学长刷题笔记

🍒 本专栏已收集 140+ 套题 🍄 题面描述等均已改编，如果和你实际看到的题面描述不一样请理解，做法和题目本质基本不变。

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

🍥 本次的T3有点困难，暂时不会正确的做法

1️⃣ 正则表达式+快速幂

2️⃣ 试除法求约数

3️⃣ 这题有点困难，暂时不会，太菜了wwww，有 AC 了的小伙伴可以教教😭

tips 正解是贪心+二分答案+数据结构，第一时间没想到正确的贪心，感谢牛友提供的思路！！！

🪙 01.多项式系数计算器

问题描述

K小姐是一位热爱代数的高中生。最近，她在研究多项式时遇到了一个有趣的问题。她有一个由若干个一次多项式因式相乘组成的表达式，每个因式的形式都是 或 ，其中 是一个非负整数。K小姐想知道，当这个表达式完全展开后， 的一次项系数是多少。

由于结果可能很大，K小姐只需要知道系数对 取模后的结果。你能帮助K小姐设计一个多项式系数计算器来解决这个问题吗？

输入格式

输入一行，包含一个字符串，表示K小姐的多项式表达式。字符串长度为 。

输出格式

输出一个整数，表示展开后 的一次项系数对 取模的结果。

样例输入

(x-1)(x+5)

样例输出

4

样例输入

(x-1)(x+2)(x+3)

样例输出

1

数据范围

• 
• 每个因式中的常数项 满足

题解

正则表达式+快速幂

多项式展开性质

对于形如 的多项式，展开后 的一次项系数等于： ，写成另一种形式，，其中

乘法逆元

在模运算中，除法可以通过乘法逆元实现。

对于质数模数 ， 的乘法逆元 满足：可以通过费马小定理计算：

算法实现

a) 使用正则表达式提取所有常数项 。 b) 计算所有 的乘积 ，同时对 取模。 c) 对每个 ，计算 ，使用乘法逆元实现除法。 d) 将所有结果相加并对 取模，得到最终答案。

参考代码

• Python

import re

def cal(expr):
    # 使用正则表达式提取常数项
    pattern = r'\(x([+-]\d+)\)'
    matches = re.findall(pattern, expr)
    
    # 将提取的常数项转换为整数
    numbers = [int(match) for match in matches]
    return numbers

mod = 10007

def inv(x):
    # 计算乘法逆元
    return pow(x, mod - 2, mod)

# 读取输入
s = cal(input())

ans = 1
for val in s:
    # 计算所有常数项的乘积
    ans *= val
    ans %= mod

res = 0
for val in s:
    # 计算最终结果
    res += ans * inv(val) 
    res %= mod

print(res % mod)

🪷 02.古董花瓶的共同特征

问题描述

K小姐是一位古董收藏家，她最近获得了四件珍贵的古代花瓶。这些花瓶来自不同的朝代，但K小姐注意到它们可能有一些共同的特征。每个花瓶都有一个特征值，K小姐想知道这四个花瓶是否存在一个大于1的共同特征因子。如果存在，她想找出最小的那个；如果不存在，她会认为这些花瓶之间没有特殊联系。

输入格式

第一行输入一个正整数 ，表示测试数据组数。

接下来 行，每行输入四个正整数 、、、，分别表示四个花瓶的特征值。

输出格式

输出 行，每行一个整数，表示四个花瓶的最小共同特征因子（大于1）。如果不存在这样的因子，输出 。

样例输入

2
2 3 5 7
4 8 16 32

样例输出

-1
2

数据范围

题解

试除法求约数

最大公约数做多了，最小公约数 ()来了你还会吗？

对最小的数求出他的所有约数，然后依次判断是否可以被成为其他所有数的公约数即可

时间复杂度： + 排序复杂度(可以不用)

参考代码

• Python

import sys
import math

def find_min_common_factor(nums):
    # 找出最小值
    min_val = min(nums)
    factors = []
    
    # 计算因数
    for i in range(1, int(math.sqrt(min_val)) + 1):
        if min_val % i == 0:
            factors.append(i)
            if i != min_val // i:
                factors.append(min_val // i)
    
    # 排序因数
    factors.sort()
    
    # 检查公因数
    for factor in factors[1:]:  # 跳过1
        if all(num % factor == 0 for num in nums):
            return factor
    
    return -1

# 读取输入
T = int(sys.stdin.readline())
for _ in range(T):
    a, b, c, d = map(int, sys.stdin.readline().split())
    print(find_min_common_factor([a, b, c, d]))

• Java

import java.util.*;

public class Main {
    public static void main(String[] args) {
        Scanner scanner = new Scanner(System.in);
        int T = scanner.nextInt();
        
        for (int t = 0; t < T; t++) {
            int a = scanner.nextInt();
            int b = scanner.nextInt();
            int c = scanner.nextInt();
            int d = scanner.nextInt();
            System.out.println(findMinCommonFactor(new int[]{a, b, c, d}));
        }
    }
    
    public static int findMinCommonFactor(int[] nums) {
        // 找出