https://www.ciyekua.cn/index.php/category/default 只是一个默认分类 https://www.ciyekua.cn/index.php/diary/167.html 2025-07-07T15:53:08+08:00 1.求next数组 ``` void get_next(int m) { ne[1]=0; for(int i=2,j=0;i https://www.ciyekua.cn/index.php/diary/166.html 2025-07-04T17:03:36+08:00 1、对于正整数a,b存在整数x,y使得gcd(a,b)=ax+by 2、整数a,b互质的充要条件是存在整数x,y使得ax+by=1 https://www.ciyekua.cn/index.php/diary/165.html 2025-05-19T17:42:56+08:00 这道题用到了贪心的思想。 在最开始我们很容易就能观察到输出-1的情况，即n个数最小和 ＞ s或最大和 < s。 将不满足题意的情况特判后，剩下来的肯定都是有解的。问题就来了，我们该怎么构造解呢？ 首先，直接暴力枚举肯定不行，然后想到是否能动态规划或贪心。这里我们选用贪心的做法。 既然我们会判断n个数的情况是否有解，我们就能判断n-1个数的情况是否有解，就这样往下递推，利用限制条件，从小到大贪心枚举，就能得出最后答案。 https://www.ciyekua.cn/index.php/diary/164.html 2025-03-07T00:36:00+08:00 例题：https://codeforces.com/problemset/problem/279/B 方法一、双指针法 代码实现：https://codeforces.com/problemset/submission/279/309233285 方法二、二分法 代码实现： https://codeforces.com/problemset/submission/279/309240075 注1：可以用`upper_bound()-1`实现不大于`x`的查找 注2：重载`lower_bound()`用的`greater()`仅适用于`从大到小`排序的数组，一定要注意！ https://www.ciyekua.cn/index.php/diary/163.html 2025-03-02T12:01:00+08:00 1.bit_width()函数：用于计算二进制有几位 https://www.ciyekua.cn/index.php/diary/162.html 2025-03-02T11:52:00+08:00 1. 相关题目：https://ac.nowcoder.com/acm/contest/103610/K 2. 洛谷日报——《浅谈素数筛优化》中提到了一个小技巧，就是有关6的优化：除2、3外的任何质数，除以6的余数一定是1或5~~~ 相关链接：https://www.luogu.com.cn/article/aqmj8yp7 https://www.ciyekua.cn/index.php/diary/160.html 2025-01-12T12:20:00+08:00 ​ 相关题目：[Problem - D - Codeforces](https://codeforces.com/contest/2043/problem/D "Problem - D - Codeforces") 解法：从大到小枚举x,y距离len（即|x-y|），然后判断gcd(x,x+len)是否==1，若==1则求出解直接return。这种方法比直接双重for循环遍历x,y快，虽然两者时间复杂度都是O(n^2)，但由于该方法是直接从len大到len小遍历的，相当于提前确定len值，找到结果能提前结束，并且找到两个距离为len的互质数又比较好找，所以跑得比较快；而双重for直接遍历不确定len值，需要完全遍历才能找到最大len值，相当于硬生生跑完了O(n^2)的复杂度，所以较慢。 写法： ​for(int len=r-l;len>=0;len--) { for(int i=l;i https://www.ciyekua.cn/index.php/diary/159.html 2025-01-09T23:32:16+08:00 众所周知，我们可以通过各个数位直接相加来判断该数是否能被3或9整除，那么，我们该如何判断一个数能否被7、11、13整除呢？这时候就需要用到 三位截断法 。 详情请见：[被7、11、13整除的整数的特点以及三位截法的原理](https://blog.csdn.net/chengyao66/article/details/131107851 "被7、11、13整除的整数的特点以及三位截法的原理") https://www.ciyekua.cn/index.php/diary/157.html 2024-08-31T13:51:00+08:00 二分搜索函数 C语言：`bsearch()` C++：`binary_search()` 1.C语言：bsearch() 函数原型如下： ``` void* bsearch( const void *key, const void *ptr, size_t count, size_t size, int (*comp)(const void*, const void*) ); ``` 2.C++：binary_search() ``` binary_search(起始地址，结束地址，要查找的数值) 返回的是是否存在这么一个数，是一个bool值。 ``` 3.C++扩展 ``` lower_bound(起始地址，结束地址，要查找的数值) lower_bound()：返回大于或等于目标值的第一个位置 upper_bound(起始地址，结束地址，要查找的数值) upper_bound()：返回大于目标值的第一个位置 ``` ``` 参考资料： https://blog.csdn.net/sinat_31608641/article/details/124975237 https://baijiahao.baidu.com/s?id=1793956676806508127&wfr=spider&for=pc ``` https://www.ciyekua.cn/index.php/diary/155.html 2024-08-16T18:08:00+08:00 在不越界的情况下，x > k 等价于$$x/2^k$$.