uva10780

将m分解质因数，然后计算次数取最小。

#include <iostream>

#include <cstdio>

#include <cmath>

#include <algorithm>

#include <vector>

#include <iomanip>

#include <cstring>

#include <map>

#include <queue>

#include <set>

#include <cassert>

#include <stack>

#include <bitset>

#define mkp make_pair

using namespace std;

const double EPS=1e-;

typedef long long lon;

const lon SZ=,INF=0x7FFFFFFF,mod=;

int n,m,res;

bool isp[SZ];

vector<int> pri;

void init()

{

    res=;

    cin>>n>>m;

}

void work(int x,int y)

{

    if(y==)return;

    res+=y/x;

    work(x,y/x);

}

int main()

{

    memset(isp,,sizeof(isp));

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

    {

        if(isp[i])

        {

            pri.push_back(i);

            for(int j=i*i;j<SZ;j+=i)

            {

                isp[j]=;

            }

        }

    }

    std::ios::sync_with_stdio();

    //freopen("d:\\1.txt","r",stdin);

    lon casenum;

    cin>>casenum;

    //cout<<casenum<<endl;

    for(lon time=;time<=casenum;++time)

    //for(lon time=1;cin>>n>>m,n;++time)

    {

        init();

        map<int,int> mp;

        int tmp=n;

        for(int i=;i<pri.size();++i)

        {

            for(;tmp%pri[i]==;)

            {

                ++mp[pri[i]];

                tmp/=pri[i];

            }

        }

        int minv=INF;

        for(auto it=mp.begin();it!=mp.end();++it)

        {

            res=;

            work(it->first,m);

            int cur=res/it->second;

            minv=min(minv,cur);

        }

        cout<<"Case "<<time<<":"<<endl;

        if(minv)cout<<minv<<endl;

        else cout<<"Impossible to divide"<<endl;

    }

    return ;

}