题解：SP1754 DIVSUM2 - Divisor Summation (Hard)

分析

我先给出一个数的约数和公式：

({a_1}^0+{a_1}^1+{a_1}^2+\cdots+{a_1}^{p_1})\times ({a_2}^0+{a_2}^1+{a_2}^2+\cdots+{a_2}^{p_2})\times ({a_3}^0+{a_3}^1+{a_3}^2+\cdots+{a_3}^{p_3})\times \cdots ({a_n}^0+{a_n}^1+{a_n}^2+\cdots+{a_n}^{p_n})

。

那么，我们就只需要求出

n

所有的质因数以及每个质因数对应的次数即可计算出最终的答案。

为此，我们可以用筛法预处理出

1 \sim 10^7

中的所有素数，用以代替枚举每个数，以达到优化时间复杂度的效果。

最后，我们只需要枚举

1\sim \sqrt{n}

中的所有素数，算出这些素数的次数，再根据上述公式，即可完成此题。

代码

CPP

#include<bits/stdc++.h>
using namespace std;
#define int long long
int vis[100000005];
vector<int> prime;
signed main(){
	ios::sync_with_stdio(false),cin.tie(0);
	vis[0]=vis[1]=1;
	for(int i=2;i<=100000000;i++){
		if(!vis[i])prime.push_back(i);
		for(int j=1;prime[j-1]*i<=100000000&&j<=prime.size();j++){
			vis[min(i*prime[j-1],100000000ll)]=true;
			if(i%prime[j-1]==0)break;
		}
	}
	int n,x;
	cin>>n;
	for(int i=1;i<=n;i++){
		cin>>x;
		int ans=1,i1=x;
		for(int j=0;prime[j]*prime[j]<=i1&&j<prime.size();j++){
			if(prime[j]==0||prime[j]==1)continue;
			int getting=1,tmp=1;
			while(i1%prime[j]==0){
				getting*=prime[j],tmp+=getting;
				i1/=prime[j];
			}
			ans*=tmp;
		}
		ans*=(1+i1);
		cout<<ans-x<<"\n";
	}
	return 0;
}

题解：SP1754 DIVSUM2 - Divisor Summation (Hard)

文章操作

题解：SP1754 DIVSUM2 - Divisor Summation (Hard)

分析

代码

相关推荐

评论

题解：SP1754 DIVSUM2 - Divisor Summation (Hard)