输入格式

测试数据第一行是一个数T（T<=10000），表示测试数据的组数。

之后每一行代表一组测试数据。

每一组测试数据有两个数，n（0<n<10^8）和m（2<=m<10^6）。

输出格式

对于每组测试数据，输出一行，每行一个数，能满足n!=k * m^p 的最大的p。

#include <cstdio>

#include <cstring>

#include <algorithm>

#include <cmath>

using namespace std;

const int N = 1e6;

typedef long long ll;

int n, m, c;

int fr[N], p[], mp[];

int pri[N]= {};

int pnum = ;

void pre()

{

    for(int i = ; i < N; ++i) {

        if(!fr[i]) {

                pri[ pnum++ ] = i;

                fr[i] = i;

        }

        for(ll j = ; j < pnum && i * pri[j] < N; ++j) {

            fr[i * pri[j]] = pri[j];

            if(!(i % pri[j])) break;

        }

    }

}

void get(int x) { /// 对x唯一分解，mp存储质因数序列，p存储每个质因数对应的个数

    c = ; int t = -;

    while(x > )

    {

        if(fr[x] != t) {

                c++;

                mp[c] = fr[x];

        }

        p[c]++;

        t = fr[x];

        x /= fr[x];

    }

}

int calc(int k) { ///求1~n中能组成的k的个数

    int cnt = ;

    ll mult = k;

    while(mult <= n)

    {

        cnt += n / mult;

        mult  = mult * k;

    }

    return cnt;

}

int main()

{

    pre();

    int _; scanf("%d", &_);

    while(_ --)

    {

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

        memset(p, , sizeof p);

        get(m);

        int ans = 0x3f3f3f3f;

        for(int i = ; i <= c; ++i)

        {

            ans = min(ans, calc(mp[i]) / p[i]);

        }

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

    }

    return ;

}