数论 - 约数 - 公式
约数
- 约数的定义
- 试除法求约数
- 约数的个数
- 约数之和
约数的定义
约数也就是一个整数的所有整数因子
试除法求约数
从小到达枚举所有的正整数，一个个判断是否是当前数的约数，当然枚举的时候可以进行优化，不用全部枚举，枚举一半的因子就能求出另一个因子了，可以将时间复杂度降低到O(sqrt(n))
代码：
#include
#include
#include
using namespace std;
setans; //由于最后要顺序输出并且不重复，因此需要保存一下
int n,a;
int main()
{cin>>n;while(n--){cin>>a;ans.clear();for(int i=1;i<=a/i;i++){if(a%i==0){ans.insert(i);ans.insert(a/i);}}for(auto i : ans){cout< 约数的个数
对于每个数，可以拆成
N = p1a1 * p2a2 * p3a3 … pkak
而对于N的某个约数，d = p1b1 * p2b2 * p3b3 … pkbk
N的每个约数由b1~bk的取值组合决定，只要b1,b2,b3…bk序列不一样，就对应不同的约数，因此这个序列的种类个数就是约束的个数，b1的取值范围为[0,a1] ，b2的取值范围为[0,a2]，b3的取值范围为[0,a3]，因此约束的个数最终为(a1+1) * (a2+1) * (a3+1)…(ak+1)
刷题链接：https://www.acwing.com/problem/content/description/872/
思路分析：咱也不能只能把全部的数乘在一起，然后进行因式分解，根本存不了那么大的数，对每个数进行单独的因式分解就行，因为质因子指数的取值序列反正是取决于每一个因子的。
AC代码：
#include
#include 约数之和
对于每个数，可以拆成
N = p1a1 * p2a2 * p3a3 … pkak
所有约数的和为：(p10+p11+…+p1a1) * (p20+p21+…+p2a2) * …
(pk0+pk1+…+pkak)
证明：把括号展开后为()+()+…+()的形式，每一项是从上面的某几个括号选出来的一个，假设某一项从第一个括号中选出的是p1b1 ，从第二个括号选出的是p2b2，从第k个括号选出来的是pkbk ，因此展开后的每一项都是p1b1 * p2b2 * …* pkbk的形式，一共有多少项呢？实际就是从每个括号中选出的数的种类数相乘，也就是(a1+1) * (a2+1) * (a3+1)…(ak+1)项，每一项其实就对应N的一个约数，总和就是这个公式
#include
#include 注意最后算和和乘积的时候要开long long，拿不准就全部都开long long
上一篇：Python GUI技术简介