题解 | #整除问题#

/*新经验：

算法逻辑完全正确，但输出陷入死循环导致超时，
不如看看循环条件的变量，是否沿用判断里的了，应该要开一个新数重新赋值。
如第62行：
int ii=i;//必须给i开新的数运算，否则就会一直死循环然后超时

*/

//牢牢记住这句话：所有数都等与  一个或多个质数相乘的形式 
#include <iostream>
#include <vector>
using namespace std;
struct zyz
{
    int x;//质因子是谁
    int y;//x的个数
    long long z;//n有多少个x因子
};

vector<zyz> vec;//每个质因子是什么，个数

void Qvec(int a)
{
    int bound=a;
    for(int i=2;i<=bound;i++)//如果a是质数，那就=bound
    {
        int count=0;
        zyz element;
        element.x=i;
        element.y=0;
        if(a%i==0)
        {  
            while(a%i==0)
            {
                element.y++;
                a/=i;
            }
            vec.push_back(element);

        }
    }
}
int main() {
    int a, n;
    while (cin >> n >> a) { 
        
        Qvec(a);//先算出a的vec
       // long long mul=1;
  

        for(int j=0;j<vec.size();j++)vec[j].z=0;

        for(int i=2;i<=n;i++)//
        {
           // mul*=i;//用这种真的去乘阶层的方法会导致超界（long long 最大19位）
           int ii=i;//必须给i开新的数运算，否则就会一直死循环然后超时
            for(int j=0;j<vec.size();j++)
            {
                while((ii!=1)&&(ii%vec[j].x==0))
                {
                   ii/=vec[j].x;
                    vec[j].z++;
                }
            }
           
        }
     //   cout<<"mul:"<<mul<<endl;//
    //    for(int j=0;j<vec.size();j++)//
      //  {
      //      cout<<"x:"<<vec[j].x<<" y:"<<vec[j].y<<" z:"<<vec[j].z<<endl;//
      //  }//


        int k=0;

        k=(vec[0].z)/(vec[0].y);
        for(int j=0;j<vec.size();j++)
        {
            if((vec[j].z)/(vec[j].y)<k)k=(vec[j].z)/(vec[j].y);
        }
        cout<<k<<endl;
    }
}