💖 ❄️我们的算法之路❄️💖
众所周知，作为一名合格的程序员，算法 能力 是不可获缺的，并且在算法学习的过程中我们总是能感受到算法的✨魅力✨。
☀️🌟短短几行代码，凝聚无数前人智慧；一个普通循环，即是解题之眼🌟☀️
💝二分，💝贪心，💝并查集，💝二叉树，💝图论，💝深度优先搜索(dfs) ，💝宽度优先搜索（bfs） ，💝数论，💝动态规划等等， 路漫漫其修远兮，吾将上下而求索！ 希望在此集训中与大家共同进步，有所收获！！！🎉🎉🎉
今日主题：数论
👉⭐️第一题💎
✨题目
✨思路：
加一得十进一位个位数为 00 加法运算如不出现进位就运算结束了且进位只会是一
所以只需要判断有没有进位并模拟出它的进位方式，如十位数加 11 个位数置为 00，如此循环直到判断没有再进位就退出循环返回结果。
然后还有一些特殊情况当出现 9999、999999 之类的数字时，循环到最后也需要进位，出现这种情况时需要手动将它进一位。
✨代码：
class Solution { public: void deal(int n, vector<int> &digits) { if(n<0){ digits.insert(digits.begin(),1); return; } if (digits[n] + 1 == 10) { digits[n] = 0; deal(n - 1, digits); } else { digits[n] += 1; } } vector<int> plusOne(vector<int> &digits) { int n = digits.size(); deal(n - 1, digits); return digits; } };
👉⭐️第二题💎
✨题目
✨思路：
由 10=2*5易得，0只能由2和5相乘得到，而在5的个数又小于2的个数，所以按照木桶原理,只需要求出阶乘中有多少5,就可以的到有多少0,可直接用递归求得
✨代码：
class Solution { public: int ans1; void deal(int n) { if (n <= 1) return; deal(n-1); while (!(n % 5)) { n /= 5; ans1++;} }; int trailingZeroes(int n) { deal(n); return ans1; } };
👉⭐️第三题💎
✨题目
✨思路：
其实就是一个数学推导的过程，首先如果 组数i为奇数，那么n必须能够整除i，并且平均数avg=n/i,avg>i/2，那么i<sqrt(2n)这样才有足够的i满足条件；当组数i为偶数时，则还要满足(2 * (n / i ) + 1) * (i / 2),随后一个for循环解决问题，时间复杂度为 O(√n)，，嗯，这是纯用数学归纳法得到，看了题解才知，原来直接用等差数列求和推出即可。。
✨代码：
class Solution { public: int consecutiveNumbersSum(int n) { int ans = 0; for (int i = 1; i < sqrt(2 * n); i++) { if (!(n % i) && i & 1) { ans++; } else if (!(i & 1)) { int t=n/i; ans += (2 * t + 1) * (i / 2) == n ? 1 : 0; } } return ans; } };
👉⭐️第四题💎
✨题目
✨代码：
q = int(input()) for _ in range(q): n, k = map(int, input().split()) s = input() if s == s[::-1] or k == 0: print(1) else: print(2)
写在最后：
相信大家对今天的集训内容的理解与以往已经有很大不同了吧，或许也感受到了算法的魅力,当然这是一定的，路漫漫其修远兮，吾将上下而求索！伙伴们，明天见！
