紫书例题 10-４ UVa 10791（唯一分解定理）

首先分解，然后可以发现同一个因子ａｉ不能存在于两个以上的数中

因为求的是最小公倍数，如果有的话就可以约掉

所以数字必然由ａｉ的ｐｉ次方的乘积组成，那么显然，在

ａ最小为２，而ｂ大于２的情况下ａ＊ｂ＞ａ＋ｂ

所以要让和最小，就每一个ａｉ的ｐｉ次方作为一个数就好了。

另外注意long long，素数和１

#include<cstdio>

#include<cmath>

#define REP(i, a, b) for(int i = (a); i < (b); i++)

using namespace std;

int main()

{

	int n, kase = 0;

	while(~scanf("%d", &n) && n)

	{

		if(n == 1) { printf("Case %d: 2\n", ++kase);  continue; }

		int m = floor(sqrt(n) + 0.5), num = 0;

		long long ans = 0;

		REP(i, 2, m)

			if(n % i == 0)

			{

				num++;

				int t = 1;

				while(n % i == 0) n /= i, t *= i;

				ans += t;

			}

		if(n > 1) num++, ans += n;

		if(num == 1) ans++;

		printf("Case %d: %lld\n", ++kase, ans);

	}

	return 0;

}

巴特西

紫书例题 10-４ UVa 10791（唯一分解定理）

最新文章

热门文章

巴特西

紫书 例题 10-４ UVa 10791（唯一分解定理）

最新文章

热门文章

紫书例题 10-４ UVa 10791（唯一分解定理）