题解 UVa10780

题目大意 多组数据，每组数据给定两个整数 \(m,n\)，输出使 \(n\%m^k=0\) 的最大的 \(k\)。如果 \(k=0\) 则输出Impossible to divide。

分析计数水题。将 \(m\) 质因数分解后在 \(1-n\) 之间试除 \(m\) 的每个素因子，统计总个数即可。

#include<bits/stdc++.h>

using namespace std;

int T, t, n, m, ans;

int tot, p[20];

map<int, int> m1, m2;

int main()

{

	scanf("%d", &T), t = 1;

	while(t <= T) {

		ans = 0x3f3f3f3f, tot = 0;

		m1.clear(), m2.clear();

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

		for(int i = 2; i <= m; ++i) {

			if(m % i) continue;

			p[++tot] = i;

			while(!(m % i)) ++m1[i], m /= i;

		}

		for(int i = 1; i <= n; ++i) {

			int tmp = i;

			for(int j = 1; j <= tot; ++j)

				while(!(tmp % p[j])) ++m2[p[j]], tmp /= p[j];

		}

		for(int i = 1; i <= tot; ++i)

			ans = min(ans, m2[p[i]] / m1[p[i]]);

		printf("Case %d:\n", t++);

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

		else puts("Impossible to divide");

	}

}

巴特西

题解 UVa10780

最新文章

热门文章