约数

AcWing 869. 试除法求约数 时间复杂度 \(O(n\sqrt a)\) #include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; vector<int ......

其中1有点特殊所以就直接从2开始了 #include<bits/stdc++.h> using namespace std; int w[2000],f[2000]; int main(){ int n; cin>>n; for(int i=1;i<=n;i++){ w[i]++; for(int ......

P1734 最大约数和 基本思路 设状态方程F[i][j]为前\(i\)个数和为\(j\)时的最大约数和。 状态转移则是F[i][j] = max(F[i - 1][j], F[i - 1][j - i] + divisorSum(i) 即要么选\(i\)，要么不选。 代码实现 WA一个点，TLE六 ......

算法学习笔记，记录容易忘记的知识点和难题。试除法、分解质因数、筛质数、约数个数、约数之和、最大公约数 ......

推荐视频：517 筛法求约数和 这个比较简单，若想来点挑战，请点开这个：P2424 约数和 点击查看代码 #include<bits/stdc++.h> using namespace std; #define LL long long const int N = 1e8 + 10; int p[N ......

推荐视频：516 筛法求约数个数 点击查看代码 #include<bits/stdc++.h> using namespace std; #define LL long long const int N = 1e8 + 10; int p[N], cnt; int d[N];//d[i]记录i的约数 ......

下面这个代码TLE了，因为做除法的速度比做乘法慢4到5倍 。 #include <bits/stdc++.h> using namespace std; long long a,b,ans,f[10000001]; int main() { cin>>a>>b; for(long long i=1; ......

选取和不超过 S 的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。 ###1. 动态规划 + 筛预处理 ``` vector prime(10e3+1,1);//约数和，即价值 int init = []() {//筛预处理 for(int i=2;i dp(V+1); long lo ......

# 两个正整数a，b，请问a∗b有哪些因子 #1≤a,b≤1e9 # 求因子的数量并给出所有因子 ### 本题无脑的暴力显然不能过，但用set存数，加上考虑到a*b的所有约数其实就是a的所有约数和b的所有约数分别相乘(核心） # 补充常识：int范围内数的约数个数最多为1600，2e9数的约数个数最 ......

# [1855B.Longest Divisors Interval](https://codeforces.com/contest/1855/problem/B "Codeforces 1855B") ## Description: - 对于一个整数 $n$ $(1\leq n \leq 10^{ ......

# 第一部分 质数的判定 ### 试除法 #### 思想： 要检验一个数字 $n$ 是否为质数，将 $n$ 除以 $1\sim \sqrt n$，如果有一个数字刚好整除 $n$，那么 $n$ 为合数，否则 $n$ 为奇数。 #### 代码： ```cpp bool prime(int x) { if ......

//POJ1845 求pow(a, b)的所有约数之和//方法：1，分解质因数，将a分解成p1^ k1* p2^ k2^...*pn^ kn//2, 那么pow(a, b)为p1 ^ (k1* b)* p2 ^ (k2* b)^...*pn ^ (kn* b)//3，对于单独的pi ^ (ki * ......

看到这种奇怪的操作，首先想到分块。 以下记值域为 $w$，块长为 $B$。 前缀 $\gcd$ 显然单调不增，而且后一个必须是前一个的因数，如果变化至少要减半。因此，我们知道，共有 $\mathcal O(\log w)$ 个不同的前缀 $\gcd$。我们可以接受对这些块暴力，只需要对前缀 $\gc ......

比较难,没怎么看懂 //约数: //如果一个数d是n的一个约数,即d能整除n,那么n/d也能整除n: //求所有约数(除法求约数,o(sqrt(n))) #include<bits/stdc++.h> using namespace std; const int N=1e5+10; int n,x; ......

请求出 $f_n$ 与 $f_m$ 的最大公约数，即 $\gcd(f_n, f_m)$，答案对 $10^8$ 取模。 结论：$\gcd(f_n, f_m) = f_{\gcd(n, m)}$ 证明如下： 首先引理 1： $$ f_{n + m} = f_{n - 1} \times f_{m} + ......

##题目链接(https://ac.nowcoder.com/acm/problem/14682) ##题意简述 给个n，求1到n的所有数的约数个数的和~（n 点击查看代码 ``` #include #define endl '\n' typedef long long ll; typedef do ......

# [最大约数和](https://www.luogu.com.cn/problem/P1734 "最大约数和") ## 题目描述 选取和不超过 $S$ 的若干个不同的正整数，使得所有数的约数（不含它本身）之和最大。 ## 输入格式 输入一个正整数 $S$。 ## 输出格式 输出最大的约数之和。 # ......

没错,数学也有分类了qaq,我之前学算法的时候妹学数学,今天算是被搞怕了(但还是不听ovo) 学会了两种方法,主要思想还是,对于每个i来说,他在从1-n中的贡献值是n/i,也就是1-n中约数含有它的数目是n/i(厉害吧,刚学的)另外一种方法是筛法,说实话这个你应该想到的(恼),不优化会爆的(30分) ......

## 质数相关 ### 一、算数基本定理 任何一个大于1的正整数都能唯一分解成有限个质数的乘积 写作： $$ n=p_1^{c1}p_2^{c2}\dots p_m^{cm} $$ $$ =\prod_{i=1}^mp_i^{ci} $$ ### 二、因数分布 若存在一个正整数 $ n $ 为合数， ......

## 题目描述 假设现在有两个自然数 A 和 B，S是 A^B的所有约数之和。 请你求出 S mod 9901 的值是多少。 ## 输入格式 在一行中输入用空格隔开的两个整数 A 和 B。 ## 输出格式 输出一个整数，代表 S mod 9901 的值。 ## 数据范围 0≤A,B≤5×10^7 # ......

约数个数和约数之和推导： 约数个数代码实现： 求n个数的乘积的约数个数： #include<iostream> #include<unordered_map> using namespace std; #define int long long const int p=1e9+7; unordere ......

题目描述 输入一个数n，输出前n个数约数的和。（约数是指若整数a除以整数b除得的商正好是整数而没有余数） 输入 输入一个整数n。 输出 输出一个整数。 样例输入 复制 7 样例输出 复制 41思路：暴力时间N方复杂度过不了，使用线性筛选：具体来说，我们可以使用一个数组sum，其中sum[i]表示正整 ......

https://www.acwing.com/problem/content/3380/ 这题和第11届蓝桥杯B组国赛题类似 数论知识,就是分解质因数,把质数的指数加1即可 需要注意的是,本题应该是不能用数组模拟的,空间太少了 可以用unordered_map存储 #include<iostream ......

约数之和 plus 0x01 背景题目 0. 定理 算术基本定理（正整数唯一分解定律）： 不考虑排列顺序的情况下，每个正整数都能够以唯一的方式表示成它的质因数的乘积。 $x={p_1}^{k_1} * {p_2}^{k_2} *{p_3}^{k_3}.....{p_n}^{k_n}$ 人话：对于每个 ......

模板: //质数判定--试除法 //朴素 O(N) bool is_prime(int n) { if(n<2)return false; for(int i=2;i<n;i++) { if(n%i==0)return false; } return true; } //朴素优化 O(sqrt(N) ......