首页 > 其他 > 详细

牛客网——整除问题

时间:2019-02-02 18:36:37      阅读:223      评论:0      收藏:0      [点我收藏+]

题目描述

给定n,a求最大的k,使n!可以被a^k整除但不能被a^(k+1)整除。

输入描述:

两个整数n(2<=n<=1000),a(2<=a<=1000)

输出描述:

一个整数.

链接:https://www.nowcoder.com/questionTerminal/8e29045de1c84d349b43fdb123ab586a
来源:牛客网

#include <bits/stdc++.h>
using namespace std;
bool isp[1000];
void isprime()//筛选求素数
{
    for(int i=2;i<=sqrt(1000);i++)
    if(isp[i]==0)for(int j=i;i*j<=1000;j++)
    isp[i*j]=1;
}
int main()
{
    int n,a,i,j,k=99999999;
    int e[1000]={0},ea[1000]={0};
    cin>>n>>a;
    isprime();
    for(i=2;i<=n;i++)//唯一分解i
    {
        int temp=i;
        for(j=2;j<=sqrt(i);j++)
        {
            if(isp[j]==1)continue;
            while(temp%j==0)
            {
                e[j]++;
                temp=temp/j;
            }
        }
        if(temp!=0)e[temp]++;
    }
    for(i=2;i<=a;i++)
    {
        if(isp[i]==1)continue;
        while(a%i==0)
        {
            ea[i]++;
            a=a/i;
        }
        if(ea[i]!=0)k=min(k,e[i]/ea[i]);
    }
    cout<<k<<endl;
}

 

牛客网——整除问题

原文:https://www.cnblogs.com/JAYPARK/p/10348931.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!