线性筛

【莫比乌斯反演】【线性筛约数和】P3312 [SDOI2014]数表

题意求∑i1n∑j1m[σ1(gcd⁡(i,j))≤a]σ1(gcd⁡(i,j))\sum_{i1}^n \sum_{j1}^m [\sigma_1(\gcd(i,j))\le a]\sigma_1(\gcd(i,j))∑i1n∑j1m[σ1(gcd(i,j))≤a]σ1(gcd(i,j)) 分析代码 #include<bits/stdc.h> using namespace std; typedef long long ll; c…

质数算法（C/C++）

目录 1 分解质因数 2 打印质数表 2.1 O（n^2）算法（暴力法） 2.2 O（nlogn）算法（埃氏筛） 2.3 O（n）算法（线性筛） 1 分解质因数 …

聪明的燕姿

题目描述分析提到约数之和，就不难想到约数个数和约数之和的两个公式对于这道题来说，如果这个数大于S，那么这个数必然有两个因子，一个1一个S，那么这个数一定不符合要求，因此只需要在1~S中考虑即可假设…

线性筛素数（欧拉筛）

线性筛法，也称为欧拉筛法，是一种高效的素数筛选算法，它可以在O(n)的时间复杂度内筛选出小于等于n的所有素数。下面是线性筛素数的基本原理和代码示例： 基本原理： 1. 初始化一个布尔数组 is_prime，将所有的…

线性筛

【算法简介】线性筛主要用于O(n)计算积性函数积性函数主要有： 还有当f(x)和g(x)都是积性函数时，狄利克雷卷积也是积性函数可以进行线性筛【素数筛】 void shai() {for(int i2;i<n;i){if(!np[i])p[pcnt]i;for(int j1;j<pcnt && p[j]…

【经典专题】寻找质数——巧妙的埃氏筛和线性筛

很经典的题目：给出nnn，统计 [2,n)[2,n)[2,n) 中质数的数量 Demo1：input 10，output 4 Demo2：input 100，output 25 暴力枚举首先，复习一遍质数的定义：在大于1的自然数中，…

ACM-ICPC 2018 南京赛区网络预赛 Sum（线性筛）

样例输入 2 5 8 样例输出 8 14 首先，平方数也就是一个数唯一分解后，有一个质因子（假设为p）的指数大于等于2。对于一个数，如果它有一个质因子的指数大于等于3，那么不管怎么分这个质因子，左乘…