【HDU6037】Expectation Division（动态规划，搜索）

题面

Vjudge

你有一个数\(n\)，\(n\le 10^{24}\)，为了方便会告诉你\(n\)分解之后有\(m\)个不同的质因子，并且把这些质因子给你。

你每次可以把\(n\)变成一个它的约数，求变成\(1\)的期望步数。

题解

首先暴力的转移是：

\[f[n]=1+\frac{1}{\sigma(n)}\sum_{d|n}f[d]
\]

不难发现这个状态之和每个质因子的出现次数的集合相关，与质因子是什么无关。

发现\(n\)本质不同的质因子最多只有\(18\)个，那么我们爆搜这个每个质因子出现次数的集合，强制较小的质因子出现次数较大，搜完之后发现状态只有\(172513\)个。

于是我们对于每个\(n\)的质因子出现个数的集合计算答案，只需要求解一个高维前缀和就可以进行转移了。

这里高维前缀和的求法，设\(g[n][j]\)表示对于\(n\)这个数（这个数是爆搜出来的，也就是满足小的质因子的出现次数不会少于大的质因子的出现次数），其前\(j\)个质因子的出现次数都相同，但是\(j\)之后的质因子出现次数小于等于当前位置的所有\(f[n]\)的和，转移的时候枚举给哪一位减一就行了。

#include<iostream>

#include<cstdio>

#include<cstring>

#include<algorithm>

#include<map>

using namespace std;

#define ll __int128

#define MAX 200200

const ll Limit=(ll)1e12*(ll)1e12;

ll n;int m,Case;

char ch[30];int a[30];

int p[]={2,3,5,7,11,13,17,19,23,29,31,37,41,43,47,53,59,61,67,71,73};

map<ll,int> M;int tot;ll val[MAX];

double g[MAX][20],f[MAX];

void dfs(int x,int lst,ll s)

{

	val[M[s]=++tot]=s;s*=p[x];

	for(int i=1;i<=lst&&s<=Limit;++i,s*=p[x])dfs(x+1,i,s);

}

int main()

{

	dfs(0,90,1);

	for(int i=2;i<=tot;++i)

	{

		ll x=val[i];for(int j=0;j<18;++j)a[j]=0;

		for(int j=0;j<18;++j)while(x%p[j]==0)++a[j],x/=p[j];

		for(int j=17;~j;--j)

			if(a[j])

			{

				int k=j;while(k<17&&a[k+1]==a[j])++k;

				g[i][j]=g[i][j+1]+g[M[val[i]/p[k]]][j];

			}

		int tmp=1;

		for(int j=0;j<18;++j)tmp*=a[j]+1;

		f[i]=(g[i][0]+tmp)/(tmp-1);

		for(int j=0;j<18;++j)g[i][j]+=f[i];

	}

	while(scanf("%s",ch+1)!=EOF)

	{

		for(int i=1,l=strlen(ch+1);i<=l;++i)n=n*10+ch[i]-48;

		scanf("%d",&m);

		for(int i=0;i<m;++i)

		{

			int p;scanf("%d",&p);a[i]=0;

			while(n%p==0)n/=p,++a[i];

		}

		sort(&a[0],&a[m]);reverse(&a[0],&a[m]);

		for(int i=0;i<m;++i)

			for(int j=1;j<=a[i];++j)

				n*=p[i];

		printf("Case #%d: %.10lf\n",++Case,f[M[n]]);

		for(int i=0;i<m;++i)a[i]=0;n=0;

	}

	return 0;

}

巴特西

【HDU6037】Expectation Division（动态规划，搜索）

【HDU6037】Expectation Division（动态规划，搜索）

题面

题解

最新文章

热门文章