紫书例题 10-3 UVa 10375 （唯一分解定理）

这道题感觉非常的秀

因为结果会很大，所以就质因数分解分开来算

非常的巧妙！

#include<cstdio>

#include<vector>

#include<cstring>

#include<cmath>

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

using namespace std;

const int MAXN = 11234;

bool is_prime[MAXN];

vector<int> prime;

int e[MAXN];

void init() //初始化质数

{

	memset(is_prime, true, sizeof(is_prime));

	is_prime[0] = is_prime[1] = false;

	REP(i, 2, MAXN)

	{

		if(is_prime[i]) prime.push_back(i);

		REP(j, 0, prime.size())

		{

			if(i * prime[j] > MAXN) break;

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

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

		}

	}

}

void add_integer(int n, int d) //表示把n的d次方质因数分解，结果存到数组e里面

{							  //例如d = 1表示乘以n，d = -1表示除以n

	REP(i, 0, prime.size()) //需要预处理好素数

	{

		while(n % prime[i] == 0) //注意这里是while

		{

			n /= prime[i];

			e[i] += d; //e[i]表示第i个素数的幂

		}

		if(n == 1) break; //节省时间

	}

}

void add(int n, int d) { REP(i, 2, n + 1) add_integer(i, d); }

int main()

{

	init();

	int p, q, r, s;

	while(~scanf("%d%d%d%d", &p, &q, &r, &s))

	{

		memset(e, 0, sizeof(e));

		add(p, 1); add(q, -1); add(p-q, -1);

		add(r, -1); add(s, 1); add(r-s, 1); 

		double ans = 1;

		REP(i, 0, prime.size()) ans *= pow(prime[i], e[i]);

		printf("%.5lf\n", ans);

	}

	return 0;

}

巴特西

紫书例题 10-3 UVa 10375 （唯一分解定理）

最新文章

热门文章

巴特西

紫书 例题 10-3 UVa 10375 （唯一分解定理）

最新文章

热门文章

紫书例题 10-3 UVa 10375 （唯一分解定理）