int范围内的整数，约数个数最多的大概是1500个
n内所有数的约数的个数=n内所有数倍数的个数=nlogn，平均下来每个数的约数的个数就是logn
约数：整数范围内的因数。（一般是正整数）
试除法求约数
- 时间复杂度为O(sqrt(n))
- 排序的时间复杂度是lognloglogn，小于sqrt(n)，所以整体的时间复杂度还是O(sqrt(n))。
- 如果是完全平方数（若一个数能表示成某个整数的平方的形式，则称这个数为完全平方数），则要注意不要重复加入该数的因子。例如，不能把9的因子3加入两次。
ACWING869 试除法求约数
题目描述：
给定n个正整数ai，对于每个整数ai,请你按照从小到大的顺序输出它的所有约数。
输入格式
第一行包含整数n。接下来n行，每行包含一个整数ai。
输出格式
输出共n行，其中第 i 行输出第 i 个整数ai的所有约数。
数据范围
1≤n≤100,
2≤ai≤2?10^9
输入样例：
2
6
8
输出样例：
1 2 3 6
1 2 4 8
AC代码：
#include <bits/stdc++.h>
using namespace std;
vector<int> get_divisors(int n)
{
vector<int> res;
for(int i=1;i<=n/i;i++)
{
if(n%i==0)
{
res.push_back(i);
if(n/i!=i)
{
res.push_back(n/i);
}
}
}
sort(res.begin(),res.end());
return res;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,a;
cin>>n;
while(n--)
{
cin>>a;
auto res=get_divisors(a);
for(auto t:res)cout<<t<<' ';
cout<<'\n';
}
return 0;
}
注意点： if(n/i!=i)这个判定的作用是，防止该数为完全平方数时，重复加入约数。
求约数个数
- 算术基本定理，又称为正整数的唯一分解定理，即：每个大于1的自然数，若不是本身就是质数，就是可写为2个以上的质数的积，而且这些质因子按大小排列之后，写法仅有一种方式。这样的分解式称为标准分解式。
- 乘法原理：做一件事，完成它需要分成n个步骤，做第一 步有m1种不同的方法，做第二步有m2种不同的方法，……，做第n步有mn种不同的方法。那么完成这件事共有 N=m1×m2×m3×…×mn 种不同的方法。
ACWING870 约数个数
给定n个正整数ai，请你输出这些数的乘积的约数个数，答案对10^9+7取模。
输入格式
第一行包含整数n。
接下来n行，每行包含一个整数ai。
输出格式
输出一个整数，表示所给正整数的乘积的约数个数，答案需对109+7取模。
数据范围
1≤n≤100,
1≤ai≤2?10^9
输入样例：
3
2
6
8
输出样例：
12
AC代码：
#include <bits/stdc++.h>
using namespace std;
const int mod =1e9+7;
long long ans=1;
unordered_map<int,int> primes;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,a;
cin>>n;
while(n--)
{
cin>>a;
for(int i=2;i<=a/i;i++)
{
while(a%i==0)
{
a=a/i;
primes[i]++;
}
}
if(a>1)primes[a]++;
}
for(auto i:primes)ans=ans*(i.second+1)%mod;
cout<<ans;
return 0;
}
注意点：
- 因为这题也要求质因数，所以代码很像之前的分解质因数的代码
- map<键,值>，键表示map下标，值表示map存的值
求约数的和
- 上面第三行就是约数和的计算式。
- sum(p,k)是我们要实现的核心函数。这个函数是用来实现等比数列求和公式的。
- 上述的sum公式是k在奇数条件下的公式，没有错，之所以最后一项是p^(k/2)，是因为c++有向下取整的功能。当k是奇数时，k=k/2+k/2+1。
ACWING97 约数之和
假设现在有两个自然数 A 和 B，S 是 A^B 的所有约数之和。
请你求出 Smod9901 的值是多少。
输入格式
在一行中输入用空格隔开的两个整数 A 和 B。
输出格式
输出一个整数，代表 Smod9901 的值。
数据范围
0≤A,B≤5×107
输入样例：
2 3
输出样例：
15
注意: A 和 B 不会同时为 0。
AC代码：
#include <bits/stdc++.h>
using namespace std;
const int mod =9901;
int fp(int a,int b)
{
int res=1;
a=a%mod;
while(b)
{
if(b&1)res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res;
}
int sum(int p,int k)
{
if(k==0)return 1;
if(k%2==0)return (p%mod*(sum(p,k-1))+1)%mod;
if(k%2)return (1+fp(p,k/2+1))*sum(p,k/2)%mod;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int a,b,res=1;
cin>>a>>b;
if(a==0)cout<<a<<'\n';
else
{
for(int i=2;i<=a/i;i++)
{
if(a%i==0)
{
int s=0;
while(a%i==0)
{
s++;
a=a/i;
}
res=res*sum(i,b*s)%mod;
}
}
if(a>1)res=res*sum(a,b)%mod;
cout<<res;
}
return 0;
}
注意点：
- 小心a=0的情况
a^b的标准分解式=a的标准分解式^b，由此可推出a^b的约数和的表达式- sum函数最后一定要取模
ACWING871 约数之和
给定 n 个正整数 ai ，请你输出这些数的乘积的约数之和，答案对 10^9+7 取模。
输入格式
第一行包含整数 n 。
接下来 n 行，每行包含一个整数 ai 。
输出格式
输出一个整数，表示所给正整数的乘积的约数之和，答案需对 10^9+7 取模。
数据范围
1≤n≤100 ,
1≤ai≤2×109
输入样例：
3
2
6
8
输出样例：
252
AC代码1（递推公式）：
#include <bits/stdc++.h>
using namespace std;
const int mod =1e9+7;
typedef long long LL;
unordered_map<int,int> primes;
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,a;
LL res=1;
cin>>n;
while(n--)
{
cin>>a;
for(int i=2;i<=a/i;i++)
{
while(a%i==0)
{
a=a/i;
primes[i]++;
}
}
if(a>1)primes[a]++;
}
for(auto i:primes)
{
int p=i.first,k=i.second;
LL t=1;
while(k--)t=(t*p+1)%mod;
res=res*t%mod;
}
cout<<res;
return 0;
}
AC代码2：（递归公式）
#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL mod=1e9+7;
unordered_map<int,int> primes;
LL fp(LL a,LL b)
{
a=a%mod;
LL res=1;
while(b)
{
if(b&1)res=res*a%mod;
b>>=1;
a=a*a%mod;
}
return res;
}
LL sum(LL p,LL k)
{
if(k==0)return 1;
if(k%2==0)return(p%mod*sum(p,k-1)+1)%mod;
if(k%2)return (1+fp(p,k/2+1))*sum(p,k/2)%mod;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n,a;
LL res=1;
cin>>n;
while(n--)
{
cin>>a;
for(int i=2;i<=a/i;i++)
{
while(a%i==0)
{
primes[i]++;
a=a/i;
}
}
if(a>1)primes[a]++;
}
for(auto i:primes)
{
int p=i.first,k=i.second;
res=res*sum(p,k)%mod;
}
cout<<res;
return 0;
}
注意点：
- 用递归公式总是错，后来我改了好几个变量为long long后好了，这至少说明递归公式还是能用的…
- 总体思想就是把每一个数都表示成标准分解式，然后把次数累加放到map里，再套用求约数和的公式。
最大公约数
-
求两个正整数 a 和 b 的 最大公约数 d
则有 gcd(a,b) = gcd(b,a%b)
证明：
设a%b = a - kb 其中k = a/b(向下取整)
若d是(a,b)的公约数 则知 d|a 且 d|b 则易知 d|a-kb 故d也是(b,a%b) 的公约数
若d是(b,a%b)的公约数 则知 d|b 且 d|a-kb 则 d|a-kb+k*b = d|a 故而d|b 故而 d也是(a,b)的公约数
因此(a,b)的公约数集合和(b,a%b)的公约数集合相同 所以他们的最大公约数也相同 证毕 -
代码就一行，十分简单：
return b ? gcd(b,a%b):a;
ACWING872 最大公约数
给定 n 对正整数 ai,bi ，请你求出每对数的最大公约数。
输入格式
第一行包含整数 n 。
接下来 n 行，每行包含一个整数对 ai,bi 。
输出格式
输出共 n 行，每行输出一个整数对的最大公约数。
数据范围
1≤n≤105 ,
1≤ai,bi≤2×109
输入样例：
2
3 6
4 6
输出样例：
3
2
#include <bits/stdc++.h>
using namespace std;
int gcd(int a, int b)
{
return b ? gcd(b, a % b) : a;
}
int main()
{
ios::sync_with_stdio(false);
cin.tie(0);
int n, a, b;
cin >> n;
while(n--)
{
cin >> a >> b;
cout << gcd(a, b) << '\n';
}
return 0;
}