题解 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");
    }
}