LOJ 2234/BZOJ 3629 聪明的燕姿（数论+DFS）

题面

传送门

分析

看到约数之和，我们首先想到约数和公式

若$ x=\prod_{i=1}^{n}p_i{k_i} $,则x的约数和为$ \prod_{i=1}^{n} \sum_{j=0}^{k_i} p_i^j$

那么我们可以DFS枚举x的质因数分解式，然后判断求出的约数和是否等于s

具体来说，我们先枚举选的质数$p_i$,对于每个$p_i$枚举他们的指数$k_i$(指数为0相当于不选)，然后计算和$tmp=1+p_i+p_i^2+\dots+p_i^{k_i}$

然后将tmp乘入当前约数和

dfs(deep,left,ans)表示当前枚举到第deep个质数，left表示s/当前和，ans表示当前的x

注意剪枝：

1.枚举质数时注意只需枚举1~sqrt(s)之间的质数，然后如果left正好等于一个大质数+1，则直接更新答案

质数的判断用$O(\sqrt n)$的试除法即可

2.枚举和时，当且仅当left能整除当前和的时候才继续更新

3.不要用sqrt函数，会很慢

代码

#include<iostream>

#include<cstdio>

#include<cstring>

#include<cmath>

#include<algorithm>

#define maxn 100000

using namespace std;

long long s;

int cnt=0;

int vis[maxn+5];

int prime[maxn+5];

void sieve(int n){

	for(int i=2;i<=n;i++){

		if(!vis[i]) prime[++cnt]=i;

		for(int j=1;j<=cnt&&i*prime[j]<=n;j++){

			vis[i*prime[j]]=1;

			if(i%prime[j]==0) break;

		}

	}

}

bool is_prime(int x){

	if(x==1) return 0;

	if(x<=maxn) return !vis[x];

	else{

		for(int i=1;i<=cnt&&(long long)prime[i]*prime[i]<=x;i++){

			if(x%prime[i]==0) return 0;

		}

		return 1;

	}

}

int sqs;

int sz=0;

long long res[maxn];

void dfs(int deep,long long left,long long ans){

	if(left==1){

		res[++sz]=ans;

		return;

	}

	if(left-1>prime[deep]&&is_prime(left-1)) res[++sz]=ans*(left-1);

	for(int i=deep+1;prime[i]*prime[i]<=left;i++){

		long long tmp=1;

		long long pow=1;

		for(int j=1;tmp+pow<=left;j++){

			pow*=prime[i];

			tmp+=pow;

			if(left%tmp==0) dfs(i,left/tmp,ans*pow);

		}

	}

}

int main(){

	sieve(maxn);

	while(scanf("%lld",&s)!=EOF){

		sz=0;

		dfs(0,s,1);

		printf("%d\n",sz);

		sort(res+1,res+1+sz);

		for(int i=1;i<=sz;i++){

			printf("%d ",res[i]);

		}

		printf("\n");

	}

}

巴特西

LOJ 2234/BZOJ 3629 聪明的燕姿（数论+DFS）

题面

分析

代码

最新文章

热门文章