题意描述

近来 IOI 专家们正在进行一项有关整数方程的研究，研究涉及到整数方程解集的统计问题，问题是这样的。

对任意的正整数 \(n\)，我们有整数方程：

\[\frac{1}{x_1}+\frac{1}{x_2}+...+\frac{1}{x_n}=1
\]

该整数方程的一个解集 \([x_1,x_2,...,x_n]\) 是使整数方程成立的一组正整数，例如 \([n,n,...,n]\)就是一个解集。

在统计解集时，IOI 专家把数据值相同但顺序不一样的解集认为是同一个解集。

例如：当 \(n=3\) 时，我们把 \([2，3，6]\) 和 \([3，6，2]\) 认为是同一个解集。

现在的任务是：对于一个给定的 \(m\)，在最多只允许 \(1\) 个 \(x_i\) 大于 \(m\) 时，求出整数方程不同解集的个数。

其中数据保证 \(n\leq 20,m\leq 100\)。

就是弱化版的埃及分数

算法分析

直接搜索就是了，没什么太大的技巧。

两个上下界剪枝：（假设当前进行到第 \(depth\) 个）

如果后 \(n-depth+1\) 个分母都取最小值（上一个的分母）还 \(<1\)，剪枝。
如果后 \(n-depth\) 个分母都取最大值（m），最后一个无穷小还 \(>1\) 剪枝。

注意精度问题和约分即可。

代码实现

#include<cstdio>

#include<iostream>

#include<algorithm>

#include<cstring>

#include<cmath>

using namespace std;

typedef double db;

const db eps=1e-15;

int n,m,ans=0;

int Gcd(int x,int y){

	while(y^=x^=y^=x%=y);

	return x;

}

void dfs(int dep,int last,int t1,int t2){

//dep 当前阶段，last 上一个分母，t1 当前的和的分子，t2 当前的和的分母。

	int G=Gcd(t1,t2);

	t1/=G,t2/=G;//约分不能少

	if(dep==n){

		if(t2-t1==1 && t2>=last) ++ans;//最后一个可以直接计算。

		return;

	}

	db t=1-(db)t1/t2;

	if(((db)(n-dep+1)/last)<t-eps) return;//剪枝 1。

	if(((db)(n-dep)/m)>t+eps) return;// 剪枝 2。

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

		dfs(dep+1,i,t1*i+t2,t2*i);

	return;

}

int main(){

	scanf("%d %d",&n,&m);

	for(int i=2;i<=m;i++) dfs(2,i,1,i);

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

	return 0;

}

完结撒❀。

巴特西

【HNOI】分数分解

题意描述

算法分析

代码实现

最新文章

热门文章