04 约数

定义：

若整数n除以整数d的余数为0，即d能够整除n，n是d的倍数，记作d|n.

通过质因子求一个数的约数

如果n可以表示成

  其中均为n的质因子

因为对于任意一个质因子都有选0个 选1个 选2个....选个共种可能，

n的约数个数为

f(n)=(+1)(+1)......(+1)=

所有约数的和为：

#include<bits/stdc++.h>

using namespace std;
const int N=1e6+10;

int prime[N],idx;
bool st[N];
//线性筛求1-n的所有质数
void init(int n){
	for(int i=2;i<=n;i++){
		if(!st[i]) prime[++idx]=i;
		for(int j=1;prime[j]*i<=n;j++){
			st[prime[j]*i]=true;
			if(i%prime[j]==0) break;			
		}
	}
}
//nprime存所有的质数,cnt存质数的个数
int nprime[N],cnt[N],k; 
//枚举每一个质数及质数的个数求出所有的约数
void dfs(int i,int d){
	if(i>k){
		cout<<d<<" ";
		return;
	}
	int p=1;
	for(int j=0;j<=cnt[i];j++){
		dfs(i+1,d*p);
		p*=nprime[i];
	}
}
int main(){
	init(N-1);
	int n;
	cin>>n;
	//找到所有的质数及个数
	for(int i=1;prime[i]<=n;i++){
		int p=prime[i];
		if(n%p==0) nprime[++k]=p;
		while(n%p==0) cnt[k]++,n/=p;
	}
	int sum=1;
	//根据公式求解质数的个数
	for(int i=1;i<=k;i++){
		sum*=cnt[i]+1;
	}
	cout<<"约数的个数为"<<sum<<endl;
	long long mul=1;
	//根据公式求所有质数的和
	for(int i=1;i<=k;i++){
		sum=1;
		long long p=1;
		for(int j=1;j<=cnt[i];j++){
			p*=nprime[i];
			sum+=p;
		}
		mul*=sum;
	}
	cout<<"约数的和为:"<<mul<<endl;
	cout<<"约数分别是:";
	dfs(1,1);
	
	return 0;
}

通过试除法求一个数的约数

对于n的约数d≤,那么n/d≥也是n的约数，n的约数都是成对出现的，有一个≥的就会有一个≤的约数，对于完全平方数n，是单独出现的，其他都是成对出现的。

因此只要扫描1~的所有数d，如果d能够整除n，那么就能找到两个约数d和n/d，时间复杂度为O()。

#include<bits/stdc++.h>

using namespace std;
int n;
int factor[2000],idx;
int main(){
	
	cin>>n;
	for(int i=1;i<=n/i;i++){
		if(n%i==0){
			factor[++idx]=i;
			if(i!=n/i) factor[++idx]=n/i;
		}
	}
	//n的约数有idx个，约数都保存在factor中
	for(int i=1;i<=idx;i++) cout<<factor[i]<<" ";
	return 0;
}

试除法的推论： n的约数的个数上界为

通过倍数法求解数列的约数

对于一个1~n的序列在求解每个数的约数时，如果通过试除法复杂度O()较高，观察到在求解每个数的约数时，都会重复枚举很多不是约数的数，如果我们只关注能够整除的约数，通过约数去找相应的数，而不是数去找约数，就会大大减少枚举的复杂度。

#include<bits/stdc++.h>

using namespace std;
const int N=500010;

vector<int> factor[N];

int n;
int main(){
	cin>>n;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=n/i;j++){
			factor[i*j].push_back(i);
		}
	}
	for(int i=1;i<=n;i++){
		cout<<i<<":";
		for(auto p:factor[i]){
			cout<<p<<" ";
		}
		cout<<endl;
	}
	return 0;
}

时间复杂度为: O(n/1+n/2+n/3+....+n/n)=O(nlogn)

使用倍数法求解区间数的约数，待验证

#include<bits/stdc++.h>

using namespace std;
const int N=500010;

vector<int> factor[N];

int l,r;
int main(){
	cin>>l>>r;
	for(int i=1;i<=r/i;i++){
		int s=ceil(l*1.0/i)*i;
		for(int j=s;j<=r;j+=i){
			factor[j-l].push_back(i);
			factor[j-l].push_back(j/i);
		}
	}
	for(int i=0;i<=r-l;i++){
		cout<<i+l<<":";
		sort(factor[i].begin(),factor[i].end());
		for(int j=0;j<(int)factor[i].size();j++){
			if(j==0) cout<<factor[i][j]<<" ";
			else if(factor[i][j]!=factor[i][j-1]) cout<<factor[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
}