共 7 篇文章
最近在精进Python，发现Python的语言特性使它能简洁优雅的描述埃筛求素数的过程，所以写篇博做个记录。 原理 更详细的内容可以参考我的这篇博文，这里只做一个简略的介绍。 筛法，顾名思义，用数去筛选。具体流程是这样的： 对于所有待选整数：2,3,4,5,6,7,8,9,10.....选择第一个素数2，筛掉它所有的倍数得到： 2,3,5,7,9,11,13,15.....接着用下一个数3，根据步骤2可以知道这“下一个数一定是素数”，用它继续筛掉自己的倍数：2,3,5,7,11,13,17.....重复这个步骤筛下去，剩下的就全是素数了 具体实现 完整代码 ```python # 构造一个奇数生成器 def _odd_iter(): n = 1 while True: n += 2 yield n # 构造筛选器 def _not_divsible(n): return lambda x : x % n > 0 # 筛法素数生成器 def _find_prime(): yield 2 # 返回第一个素数"2" it …
传送门 题目大意 有t(t<1e5)次查询，每次查询给出两个数a,b(a,b<2e6)。输出一组满足下列要求的四个正整数cdef作为答案。若不存在满足条件的cdef，则输出"-1 -1 -1 -1" [图片缺失] 原图：https://uploadfiles.nowcoder.com/images/20200719/272741694_1595159660992_6C354C0B6A13C2EFCC877EBE585BFDD3 ```cpp #include using namespace std; typedef long long ll; int a, b, g, t; ll c, d, e, f; int gcd( int a, int b ) { if ( b == 0 ) return(a); return(gcd( …
传送门 题目大意 现有函数 [图片缺失] 原图：https://www.nowcoder.com/equation?tex=%5Cbegin%7Balign%7D%0Af_c(x)%26%3D%5Cmax_%7Bi%3D1%20%5Cdots%20x-1%7D%20c%20%5Ccdot%20f_c(%5Cgcd(i%2C%20x))%20%26%20x%20%3E%201%5C%5C%0Af_c(x)%26%3D1%20%26%20x%3D1%0A%5Cend%7Balign%7D 给定一些正整数对(ni, ci)，输出fci(ni)在模1e9+7意义下的函数值。 思路 观察公式不难看出fc(x)=ck，k与函数递归次数相关。要求到最大值，贪心的想法是尽可能多地递归，这样就能累乘到更多的c。最好的情况是每次递归都只消去一个 质因子，这样k=质因子的个数。 实现上，从x开始递归 ，找每个数除了自己外最大的因数，直到当前数是质数或1。记录这个过程中递归层数，这个层数就是k。可以先预存好值来提升效率。 ```cpp #include using namespace std; typedef long long ll; const int LIM = 1e6 + 10; const ll MOD = 1e9 + 7; //arr[i]中存i的质因子个数 int arr[LIM], t, n, …
传送门 题目大意： 给出n个点，圆心和半径任意取的情况下，要求这n个点尽可能多的点出现在圆上。该圆一定经过坐标原点(0,0)。求满足要求的圆上至多有多少个点。 思路很清晰，三点确定一个圆，题目中又给死了一个点，那么O(n²)枚举剩下的两个点，把找到的圆心放在集合里，然后再去找出现次数最多的圆心枚举圆上点就可以了。 三点共圆圆心的寻找公式如下： [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/07/IMG_392620200716-011621-1024x981.jpg 那么不难得到它的代码表达： ```cpp point findCenter(const point &p;, const point &q;, const point &r;) { double a = 2 * (p.x - q.x); double b = 2 * (p.y - q.y); double c = p.x * p.x + …
传送门 题目大意： [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/07/equation-1024x94.png 答案一定是一个有理数，以n=p·q-1的形式并模上998244353给出。 q-1 表示q的逆元，可以用扩欧或费马小定理来算。 如果p是一个质数，而整数a不是p的倍数，则有a(p-1)≡1(mod p) 费马小定理 有两个数a,b，对它们进行辗转相除法，可得它们的最大公约数——这是显然地。然后，收集辗转相除法中产生的式子，倒回去，可以得到ax+by=gcd(a,b)的整数解，它可以用来计算模反元素(也叫模逆元)。扩展欧几里得算法 [图片缺失] 原图：https://www.edisoncgh.com/wp-content/uploads/2020/07/IMG_390520200714-224509-1024x931.jpg ```cpp #include using namespace std; typedef long long ll; int const LIM = 2e6 + 5; int const MOD = 998244353; ll n; ll fac[LIM]; ll qmod(ll …
A有趣的数字 我们称一个数是质数，而且数位中出现了 5 的数字是有趣的。例如 5,59,457 都是有趣的，而 15,7 不是。求 1 到 100000 中有趣的数的个数。 没啥好说的，就硬来。先用筛法打出素数表，再用check函数确认数位里是否含5。时间复杂度肯定是不优的，但填空题嘛能解出来就是AC。最后答案是3282. ```cpp #include #include #include #include #define get(x) scanf("%d", &x;) #define lget(x) scanf("%lld", &x;) #define set(a,b) memset(a, b, sizeof(a)) #define rep(a, b, c) for (int a = b; a <= c; a++) using namespace std; typedef long long ll; const int …
筛法 计算机中常使用筛法来计算素数。筛法的基本思想都是从一个区间中删去不符合要求的数，从而得到一个符合要求的区间，所以形象的称呼为筛法。 埃拉托斯特尼筛法(埃筛) 它又叫线性筛。埃筛可以快速获取小于等于n的素数集合。首先明确一点：对于任意合数x，它必有一个小于等于sqrt(x)的因子，因为如果两者均大于sqrt(x)那么其积必大于x。那么判断x是否为素数只需要判断2~sqrt(x)能否与x整除即可，如果一直计算到sqrt(x)都没有出现x的因数那x就是一个素数了。 埃筛基于以下原理：对于一个素数n(n>1)，它的k(k>1)倍数一定是一个合数。 假设要计算100以内的素数，从2开始遍历。 将2在100以内的所有倍数标记为合数。指针后移，检查3是否为合数。3不是合数，那么把3的所有倍数也标记为合数。指针后移，检查4是否为合数。4已经被标记为合数，跳过它。重复上述流程一直到sqrt(100)。 事实上埃筛可以进行优化，即每次标记从大于等于自身的倍数开始进行。如5，只要标记5 × 5, 5 × 6, 5 × 7…为合数，因为5 × 2, 5 × 3, 5 × 4…已经被之前出现的数的倍数标记过了。 ```cpp //时间复杂度O(sqrt(n)) void findPrimes(int n) { int p[n]; p[0] = 0;//放个0占位 int s = sqrt(n); for (int i = 2; i <= s; i++)//从2到sqrt(x)计算 if (p[i] …