JLOI2014 聪明的燕姿

wjh15101051's space

卧薪尝胆，厚积薄发。

JLOI2014 聪明的燕姿

Date: Thu Sep 06 07:46:07 CST 2018

In Category: NoCategory

Description：

给出一个数 $S$ ，求出所有满足正约数之和等于 $S$ 的数 $N$ 。

$1\le k \le 100,1\le S \le 2\times 10^9$

Solution：

首先根据唯一分解定理 $\begin{align}N=\prod_{i=1}^kp_k^{q_k}\end{align}$ ，则 $N$ 的约数个数和为 $\begin{align}\sigma_1(N)=\prod_{i=1}^k\sum_{j=0}^{q_k}p_k^j\end{align}$ 。

然后先筛出来 $1$ ~ $\sqrt S$ 的所有质数，对于 $\ge\sqrt S$ 的可以最后特判，然后每轮暴力枚举 $p_k$ 和 $q_k$ 转移，复杂度不知道。

Code：


#include

#include

#include

#include

#include

#include

using namespace std;

#define MAXK 100000

typedef long long ll;

int prime[MAXK],tot = 0;

bool isprime[MAXK];

void sieve()

{

	for(register int i = 2;i < MAXK;++i)isprime[i] = true;

	for(register int i = 2;i < MAXK;++i)

	{

		if(isprime[i])prime[++tot] = i;

		for(register int j = 1;j <= tot && i * prime[j] < MAXK;++j)

		{

			isprime[i * prime[j]] = false;

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

		}

	}

	return;

}

ll sqrts;

bool check(ll k)

{

	if(k < MAXK)return isprime[k];

	for(register int i = 1;(ll)prime[i] * prime[i] <= k;++i)

		if(k % prime[i] == 0)

			return false;

	return true;

}

int ans[MAXK],top;

void dfs(int k,ll s,int val)

{

	if(s == 1){ans[++top] = val;return;}

	if(s - 1 > sqrts && check(s - 1))ans[++top] = val * (s - 1);

	for(register int i = k + 1;prime[i] <= sqrts;++i)

	{

		register ll w = 1,t = prime[i];

		for(register int j = 1;w + t <= s;++j)

		{

			w = w + t;

			if(s % w == 0)

			{

				dfs(i,s / w,val * t);

			}

			t = t * prime[i];

		}

	}

	return;

}

int main()

{

	sieve();

	register ll s;

	while(~scanf("%lld",&s))

	{

		top = 0;sqrts = sqrt(s);

		dfs(0,s,1);

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

		sort(ans + 1,ans + 1 + top);

		for(register int i = 1;i <= top;++i)

		{

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

			if(i == top)puts("");

			else putchar(' ');

		}

	}

	return 0;

}

In tag: 算法-搜索

wjh15101051