Codeforces Round #828 (Div. 3) E2. Divisible Numbers （分解质因子，dfs判断x,y）

题目链接

题目大意

　给定a,b,c,d四个数，其中a<ｃ,ｂ＜ｃ,现在让你寻找一对数(x,y),满足一下条件：

　1. a<x<c,b<y<d

　2. (x*y)%(a*b)==0

题目思路

　因为(x*y)%(a*b)==0\(\rightarrow\)x*y\(~\)=\(~\)k*a*b\(~\)=\(~\)k*k1*k2

　所以我们要找的就是a,b的因子来保证a%k1\(~\)||\(~\)a%k2\(~\)||\(~\)b%k1\(~\)||\(~\)b%k2为0

　而每个数都能被拆成多个质因子的k次的乘积，也就是说：

　a\(~\)=\(~\)P\(_{1}\)\(^{k1}\)\(~\)*\(~\)P\(_{2}\)\(^{k2}\)\(~\)*\(~\)P\(_{3}\)\(^{k3}\)\(~\)*....*\(~\)P\(_{n}\)\(^{kn}\)

　b\(~\)=\(~\)S\(_{1}\)\(^{k1}\)\(~\)*\(~\)S\(_{2}\)\(^{k2}\)\(~\)*\(~\)S\(_{3}\)\(^{k3}\)\(~\)*....*\(~\)S\(_{n}\)\(^{kn}\)

\(~~~\)而且在质因子较少，便于搜索，所以我们直接拆出a,b的质因子去爆搜看能不能找到对应的x,y

代码详情

# include<iostream>

# include<bits/stdc++.h>

using namespace std;

# define int long long

# define endl "\n"

const int N = 5e5 + 10;

map<int, int> mp;

vector<pair<int, int>> fac;

int a, b, c, d;

bool ok = false;

void fj(int n) //分解质因数

{

	for (int i = 2; i * i <= n; ++i) {

		if (n % i == 0) {

			int cnt = 0;

			while (n % i == 0) {

				n /= i;

				cnt++;

			}

			mp[i] += cnt;//保存质因数的次数k

		}

	}

	if (n > 1) mp[n]++;

}

int ans_x, ans_y;

void dfs(int id, int k1, int k2) {

	if (id == fac.size()) {

		int x = ((a / k1) + 1) * k1;

		int y = ((b / k2) + 1) * k2;

		if (x <= c && y <= d) {

			ok = true;

			ans_x = x;

			ans_y = y;

		}

		return;

	}

	int p = fac[id].first, cnt = fac[id].second;

	int pow = 1;

	for (int i = 1; i <= cnt; ++i) pow *= p;

	int res = 1;

	for (int i = 0; i <= cnt; ++i) {

		dfs(id + 1, k1 * res, k2 * (pow / res));

		res *= p;

	}

}

void solve() {

	mp.clear(), fac.clear();

	ok = false;

	cin >> a >> b >> c >> d;

	fj(a);

	fj(b);

	for (auto p : mp) fac.push_back(p);

	dfs(0, 1, 1);

	if (ok) cout << ans_x << " " << ans_y << endl;

	else cout << -1 << " " << -1 << endl;

}

int tt;

signed main() {

	ios::sync_with_stdio(false);

	cin.tie(0);

	cout.tie(0);

	tt = 1;

	cin >> tt;

	while (tt--)solve();

	return 0;

}

巴特西

Codeforces Round #828 (Div. 3) E2. Divisible Numbers （分解质因子，dfs判断x,y）

题目链接

题目大意

题目思路

代码详情

最新文章

热门文章