首页 技术 正文
技术 2022年11月23日
0 收藏 435 点赞 3,917 浏览 894 个字

链接:https://www.nowcoder.com/acm/contest/197/A
来源:牛客网

时间限制:C/C++ 1秒,其他语言2秒
空间限制:C/C++ 262144K,其他语言524288K
64bit IO Format: %lld

题目描述

令 X = n!, 给定一大于1的正整数p 求一个k使得 p ^k | X 并且 p ^(k + 1) 不是X的因子。

输入描述:

两个数n, p (1e18>= n>= 10000 >= p >= 2)

输出描述:

一个数
表示k

<!–
–>

输入例子:
10000 12
输出例子:
4996

–>

示例1

输入

复制

10000 12

输出

复制

4996解题思路:想说比赛的时候数据范围看错了,一直段错误的要哭了。。。首先,我们知道对于任意一个数,我们都可以把他拆分成若干素因子乘积的形式如n=p^x+q^y+……r^z(p,q,……,r为素数),因为p<=n,所以p一定是n!的一个因子,所以p中含有的素因子n!中必定含有,并且幂次小于等于n!中该素因子的幂次。我们需要求一个k使得 p ^k | X 并且 p ^(k + 1) 不是X的因子,所以我们只要求p分解所得的每个素因子x的幂次ccount(x),对应于n!素因子分解中x的幂次count(x),用count(x)/ccount(x)再取最小值即为答案。附上代码:
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,p,cnt;
ll count(ll k) //计算x!的质因数分解中质因子k的幂
{
ll tot=,x=n;
while(x)
{
tot+=x/k;
x/=k;
}
return tot;
}
ll ccount(ll x) //计算x的质因数分解中质因子y的幂
{
ll tot=;
while(p%x==)
{
tot++;
p/=x;
}
return tot;
}
int main()
{
scanf("%lld%lld",&n,&p);
ll ans=1e18;
for(int i=;i<=p;i++)
if(p%i==)
ans=min(ans,count(i)/ccount(i));
printf("%lld\n",ans);
return ;
}
相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:9,254
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:5,692
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:569 阅读:6,531
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:6,302
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:7,942
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:5,102