腾讯2024技术研究岗-实习生笔试总结

腾讯2024技术研究岗-实习笔试

在牛客上考的，5道编程题，可以用本地IDE，但不能使用已有代码

前四题都比较简单，枚举、贪心、二分、最短路的考点，大概40分钟做完，第五题卡住了，到最后也没做出来

第五题是一道数学题，大体的题意忘记了，但是最后我的做法简化出来的难点应该在处理大质数\(p\)(\(1<=p<=1e9\))求\(1/p\)的循环节，看复杂度是要在\(O(\log p)\)或\(O(sqrt(p))\)，后者复杂度比较极限，因为有\(q(1<=q<=1e5)\)个询问。

考前还看了一下费马小定理，比较显然绝对能在\(O(p-2)\)的时间里求出来，用\(10\)的幂次去模拟一下除法然后求余就行，最后也大概用这个方法加一些打表的乱搞做出来\(10\)%。

考试的时候就感觉可能是扩展欧几里得之类的，但是当时数论有关的都没好好学（啊————），并且手头上也没有板子，出来看好像就是，趁这个机会在这篇里面整理一下扩欧：

费马小定理

如果 $ p $ 是一个质数，而 $ a $ 是任何不被 $ p $ 整除的整数，则有$$ a^{p-1} \equiv 1 \ (\text{mod}\ p) $$

扩展欧几里得

扩展欧几里得算法是欧几里得算法（又叫辗转相除法）的扩展。除了计算a、b两个整数的最大公约数，此算法还能找到整数x、y（其中一个很可能是负数）。通常谈到最大公因子时, 我们都会提到一个非常基本的事实: 给予二整数 \(a\) 与 \(b\), 必存在有整数 \(x\) 与 \(y\) 使得\(ax + by = gcd(a,b)\)。有两个数\(a,b\)，对它们进行辗转相除法，可得它们的最大公约数——这是众所周知的。然后，收集辗转相除法中产生的式子，倒回去，可以得到\(ax+by=gcd(a,b)\)的整数解。

可以在\(\log\)的时间复杂度内求解该数\(x\)和\(y\)

def ext_euclid(a, b):     
    if b == 0:         
        return 1, 0, a     
    else:         
        x, y, q = ext_euclid(b, a % b) 
        # q = gcd(a, b) = gcd(b, a%b)         
        x, y = y, (x - (a // b) * y)         
        return x, y, q

具体怎么用在同余方程或者说求循环节上，留个坑待填

总结

还是要时刻去复习一下一些小的知识点，感觉经常做点题去撞撞知识点适当复习一下是比较必要的，考场上写最短路都手生了，打ACM打多了板子全忘了，还是不能太依赖板子