曾经做过一个类似的  求n！中有多少个质因子m

这里有一个结论 k = n/m+n/(m^2)+n/(m^3)+....

int getnum(int n, int m)

{

    int sum = 0;

    while(n)

    {

        sum += n/m;

        n /= m;

    }

    return sum;

}

然后这个题就比较容易了

/*************************************************************************

    > Author: xlc2845       > Mail: xlc2845@gmail.com

    > Created Time: 2013年10月24日 星期四 16时15分17秒

 ************************************************************************/

#include <iostream>

#include <cstdio>

#include <cstdlib>

#include <cmath>

#include <vector>

#include <cstring>

#include <algorithm>

#define maxn 210

#define INF 0x7fffffff

using namespace std;

bool flag[5010];

int prime[5010];

void GetPrime()

{

    memset(flag, 0, sizeof(flag));

    int p = 0;

    for(int i = 2; i < 5001; i++)

    {

        if(!flag[i])

        {

            prime[p++] = i;

            for(int j = i+i; j < 5001; j+=i)

                flag[j] = 1;

        }

    }

}

int getnum(int n, int m)

{

    int sum = 0;

    while(n)

    {

        sum += n/m;

        n /= m;

    }

    return sum;

}

int main()

{

    GetPrime();

    int t,n,m,ca = 1;

    scanf("%d",&t);

    while(t--)

    {

        int p = 0, ans = INF;

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

        while(m > 1)

        {

            int k = 0;

            while(m % prime[p] == 0)

            {

                k++;

                m /= prime[p];

            }

            if(k)

                ans = min(getnum(n, prime[p])/k, ans);

            p++;

        }

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

        if(ans)

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

        else

            puts("Impossible to divide");

    }

    return 0;

}