九度oj 题目1104：整除问题
2024-09-08 07:32:22
- 题目描述：
-
给定n，a求最大的k，使n！可以被a^k整除但不能被a^(k+1)整除。
- 输入：
-
两个整数n(2<=n<=1000)，a(2<=a<=1000)
- 输出：
-
一个整数.
- 样例输入：
-
6 10
- 样例输出：
-
1 这道题貌似简单，但对n!，当n = 1000，其值远远超过int的范围，因此不能用简单的方法来求解。
考虑到整除的问题，可以将a拆分成几个质因子的乘积，记录每个质因子的个数，之后对于i从1到n，求解每一个i包含这些质因子的个数并求和。最后算和里总共包括多少个a的质因子个数，即可得出答案
代码如下#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <string>
#include <cmath>
#define MAX 1002
// 15 14 13 12 11 10 8 6 5 4 2 1
// 10 2 5
bool isPrime(int n) {
if(n <= ) {
return false;
}
else if(n == ) {
return false;
}
else {
int two = sqrt(n);
for(int i = ; i <= two; i++) {
if(n % i == ) {
return false;
}
}
return true;
} } int yin[MAX];
int prime[MAX];
int yinCount[MAX];
int yinNum[MAX]; int main(int argc, char const *argv[])
{
int n, a;
int j = ;
for(int i = ; i < MAX; i++) {
if(isPrime(i) == true) {
prime[j] = i;
j++;
}
}
int pC = j;
while(scanf("%d %d",&n,&a) != EOF) {
j = ;
memset(yinCount,,sizeof(yinCount));
memset(yinNum,,sizeof(yinNum));
for(int i = ; i < pC && prime[i] <= a; i++) {
if(a % prime[i] == ) {
int temp = a;
int tempCount = ;
while(temp % prime[i] == ) {
temp = temp/prime[i];
tempCount++;
}
yin[j] = prime[i];
yinNum[j] = tempCount;
j++;
}
} for(int i = ; i <= n; i++) {
for(int k = ; k < j; k++) {
if(i % yin[k] == ) {
int temp = i;
int tempCount = ;
while(temp % yin[k] == ) {
temp = temp/yin[k];
tempCount++;
}
yinCount[k] = yinCount[k] + tempCount;
}
}
} /* for(int i = 0; i < j; i++) {
printf("%d %d %d\n",yin[i],yinNum[i],yinCount[i]);
}*/
// 1 2 3 4 5
// 2 2 2 2 2
int ans = ;
bool flag = true;
while(flag) {
for(int i = ; i <= j; i++) {
yinCount[i] = yinCount[i] - yinNum[i];
if(yinCount[i] < ) {
flag = false;
break;
}
}
if(flag == true) {
ans++;
}
} printf("%d\n",ans);
}
return ;
}
最新文章
- HTML5学习总结-番外05 移动终端适配
- Postgresql允许远程访问配置修改
- LeetCode-Search a 2D Matrix
- OpenMP之求和（用section分块完成）
- FM四舍五入_从小数点最后一位进位
- Ajax做分页
- paper 43 ：ENDNOTE下载及使用方法简介
- 第二次正式java web开发项目的总结（回收站恢复）
- 用iframe设置代理解决ajax跨域请求问题
- linux系统的文件类型学习
- java线程（2）-线程间通信
- Java编程常见问题汇总
- printf 对齐
- ural 1118. Nontrivial Numbers
- Oracle：如何使用PL/SQL 11.0连接远程Oracle12c服务器？
- xml 制作 RSS 订阅源
- Java设计模式---ChainOfResponsibility责任链模式
- 第二节：深入剖析Thread的五大方法、数据槽、内存栅栏。
- 跨域学习笔记2--WebApi 跨域问题解决方案：CORS
- windows的tasklist使用