P1069 细胞分裂

作者

[永遠の記憶 ~ Precious Memories]施工D3

2020.3.5

转载自luogu

P1069 细胞分裂

Noip2009 T3
题目传送门

一道数学题，上手先分析
题目主要描述了这么一个东西
给定m1,m2两个量
还有n个基数S
求(S[i] ^ x) | m1 ^ m2中x的最小值
其实如果当年我在考场上的话，要求x的最小值，我肯定就直接把S[i]的最大值求出来然后除了，因为这样比较好混分(大雾

思路比较简单，我们可以分别将S[i]和m1分解，
然后去判断m1所包含的所有素因数中S[i]中是否都有，
如果没有的话，就可以直接continue，
如果全部都有的话这一项的结果就是
m1中每个素因数与S[i]中每个对应素因数次数差的最大值+1
答案就让我们求最小的这个值

有了以上的思路，我们就可以去实现了
代码如下:

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const ll maxn = 1e4+5;
const ll maxm = 3e4+5;
ll n;
ll m1, m2;
ll m1_p[maxm];
ll s[maxn];
ll ans[maxn];
ll idxm1, idxsi;
bool flag = false;
ll ret = 1e7;

int divide_prime(ll x) {
	int i = 2;
	int idx = -1e7;
	while (x != 1) {
		while (x % i == 0) {
			m1_p[i]++;
			x /= i;
		}
		idx = max(idx, i);
		m1_p[i++] *= m2; // 次数  
	}
	return idx;
}

int main() {
	scanf("%lld", &n);
	scanf("%lld%lld", &m1, &m2);
	if (m1 == 1) {
		cout << 0 << endl;
		return 0;
	}
	idxm1 = divide_prime(m1);
	for (ll i = 1; i <= n; ++i) {
		ll maxx = -100000;
		flag = false;
		scanf("%lld", &s[i]);
		for (ll j = 2; j <= idxm1; ++j) {
			if (!m1_p[j]) {
				continue;
			}
			else {
				ll temp = 0;
				while (s[i] % j == 0) {
					s[i] /= j;
					++temp;
				} // 分解顺便记次数 
				if (!temp) {
					flag = true;
					break;
				} // 没有这一项  
				maxx = max(maxx, (m1_p[j] - 1) / temp); // 因为前面乘过了，所以这里是除  
			}
		}
		if (flag) {
			ans[i] = -1;
		}
		else ans[i] = maxx;
	}
	for (ll i = 1; i <= n; ++i) {
		if (ans[i] != -1) {
			ret = min(ans[i], ret);
		}
	}
	if (ret == 1e7) {
		printf("-1\n");
	}
	else {
		printf("%lld\n", ret + 1);
	}
	return 0;
}

在写的时候，出现了很多神奇的问题

  1. 前面的素因数分解，不能用for(int i = 2; i * i <= n; ++i)亲测会爆两个点
  2. 当m1 == 1时必须特判，不然第一个点会WA
  3. 代码中求maxx那一行中必须要是(m1_p[j] – 1)不能是m1_p[j]，不然会WA(具体什么原因我也不是很清楚，希望能有dalao解释一下。。。
  4. 最后输出的答案必须加1，这个很好理解，因为刚开始的时候也算一次

另外，感谢@24680esz 大佬的题解，上述的许多问题都是研究完题解才发现的

[写在最后]
这道题目总体难度不是很大，主要考察选手的仔细程度，但是想必当年这道题还是卡了不少人吧(雾
要是我当年正好在考场上的话，推出规律应该不难，但是能不能写出完整的代码就是个问题了，因为考场上毕竟还是很紧张的
现在正好能宅在家里，有空写点题，要是在上学的时候估计是写不出来的，因为那时候戾气太重了
先写到这里吧，已经晚上十一点半了
ps:希望能过审！

发表评论