题解 | #整除问题#

#include <iostream>
#include <cstdio>
#include <cmath>
#include <vector>
#include <map>
using namespace std;
const int MAXN=1001;
int main()
{
    int n,a,k,i,t,j,mk,f;
    //cout<<6*5*4*3*2<<endl;
    map<int,int> s1,s2;
    bool isprime[MAXN];
    vector<int> prime;
    for(i=0;i<MAXN;i++)
        isprime[i]=true;
    isprime[0]=isprime[1]=false;
    for(i=2;i<MAXN;i++)
    {
        if(!isprime[i])
            continue;
        prime.push_back(i);
        for(j=i*i;j<MAXN;j=j+i)
            isprime[j]=false;
    }
    while(cin>>n>>a)
    {
        s1.clear();
        s2.clear();
        t=a;
        for(i=0;prime[i]<=a;)
        {
            if(t%prime[i]==0)
            {
                t=t/prime[i];
                if(s1.find(prime[i])!=s1.end())
                    s1[prime[i]]++;
                else
                    s1[prime[i]]=1;
                if(t==1)
                    break;
            }
            else
                i++;
        }
        for(k=2;k<=n;k++)
        {
            t=k;
            for(i=0;prime[i]<=k;)
            {
                if(t%prime[i]==0)
                {
                    t=t/prime[i];
                    if(s2.find(prime[i])!=s2.end())
                        s2[prime[i]]++;
                    else
                        s2[prime[i]]=1;
                    if(t==1)
                        break;
                }
                else
                    i++;
            }
        }/*
        for(map<int,int>::iterator it=s2.begin();it!=s2.end();it++)
            cout<<it->first<<":"<<it->second<<' ';
        cout<<endl;
        for(map<int,int>::iterator it=s1.begin();it!=s1.end();it++)
            cout<<it->first<<":"<<it->second<<' ';
        cout<<endl;*/
        mk=0;
        f=1;
        i=1;
        while(f)
        {
            for(map<int,int>::iterator it=s1.begin();it!=s1.end();it++)
            {
                if(s2.find(it->first)!=s2.end()&&s2[it->first]>=it->second*i)
                {
                    continue;
                }
                else
                {
                    f=0;
                    break;
                }
            }
            if(f==1)
            {
                mk=i;
                i++;
            }
            else
            {
                break;
            }
        }
        cout<<mk<<endl;

    }
    return 0;
}