整除问题
http://ac.jobdu.com/problem.php?id=1104
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
#include<memory.h>
int prime[170],num;
void findPrime(int n)
{
int i,j,k,flag;
prime[0]=2;
num=1;
for(i=3;i<=n;i+=2) //奇数才有可能是素数,偶数就可以直接忽略了
{
k=sqrt(i*1.0);
flag=0;
for(j=3;j<=k;j+=2) //奇数肯定无法整除偶数,所以只需要判断是否能否整除奇数就可以了,只要有一个能够整除,就不是素数
{
if(i%j==0)
{
flag=1;
break;
}
}
if(flag==0)
prime[num++]=i;
}
}
int main(void)
{
int i,n,a,p,m,hash[1000],h,max;
findPrime(1000);
while(scanf("%d %d",&n,&a)!=EOF)
{
max=1000;
memset(hash,0,sizeof(hash));
for(i=0;prime[i]<=a && i<num;i++)
{
p=prime[i];
m=0;
while(a%p==0)
{
m++;
a/=p;
}
hash[p]=m;
if(a==1)
break;
}
h=n;
p=2;
for(m=0;h/=p;) //n!中2的个数可表示为 n/2+n/4+...
m+=h;
if(hash[2])
{
if(m/hash[2]<max)
max=m/hash[2];
}
for(i=3;i<1000;i+=2)
{
if(hash[i])
{
p=i;
h=n;
for(m=0;h/=p;) //道理同上
m+=h;
if(m/hash[i]<max)
max=m/hash[i];
}
}
printf("%d\n",max);
}
return 0;
}
分享到:
相关推荐
上海交大计算机专业历年考研真题.CHM上海交大计算机专业历年考研真题.CHM上海交大计算机专业历年考研真题.CHM上海交大计算机专业历年考研真题.CHM
上海交通大学05-07年上机真题,内附答案,为那些打算考研或保研到上海交大同学准备
最近几年上海交大考研真题和答案
上海交大计算机考研2004真题(答案) 上海交大计算机考研2004真题(答案) 上海交大计算机考研2004真题(答案) 上海交大计算机考研2004真题(答案)
2018年西南交大计算机数据结构考研真题2018年西南交大计算机数据结构考研真题
上海交大《计算方法》考博真题
上海交通大学815控制理论基础2011年真题回忆版,题型真实,2012年真题相对2011年有比较大的改动,但仍然保留了2011年的一些题型
上海海事大学考研真题,主要考试内容为数据结构,上海海事大学计算机考研必备,欢迎大家下载使用,真题为15-18年,近两年真题未收录,整体考试内容变化不大
交通大学819 回忆版的真题,看一看还是不错的
2011年计算机考研统考专业课真题加解析
该资源为2021年上海交通大学834考研真题,资源高清无水印哦!
资源包括上海交通大学431金融真题,考生考完第二天回忆整理而成,同时还有一些报考建议,上海交大金融专硕考研专业课存在严重的信息差,这份文件非常有价值!
2011年计算机考研统考真题及详细解析
计算机技术与软件专业技术资格(水平)考试--信息系统监理师--历年真题--2011年下半年信息系统监理师真题(无答案)PDF版
2017年西南交大计算机数据结构考研真题2017年西南交大计算机数据结构考研真题
2011年1月计算机原理自考真题.pdf
2011年计算机考研真题及答案完整版,2011年408真题及答案解析
上海市计算机一级考试历年真题操作题,考计算机一级的可以来看一看
上海交大历年自控考研真题 97-06年,难得的好资料。