题记(23)--整除问题

发布时间:2024年01月22日

目录

一、题目内容

二、输入描述

三、输出描述

四、输入输出示例

五、完整C语言代码


一、题目内容

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

二、输入描述

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

三、输出描述

一个整数.

四、输入输出示例

输入:

6 10

输出:

1

五、完整C语言代码

AC代码~
#include<stdio.h>

int num1[1001]; // 存储n!的质因数 
int num2[1001]; // 存储a的质因数 
int main(){
	int a,n,k;
	k = 9999;
	for(int i=0;i<1001;i++){
		num1[i] = 0;
		num2[i] = 0;
	}
	scanf("%d%d",&n,&a);
	for(int i=2;i<=n;i++){
		int t=i;
		int j = 2;
		while(t!=1){// 质因数分解 
			if(t%j == 0){
				num1[j]++;
				t = t/j;
			}
			else
				j++;
		}
	}
	int j = 2;
	while(a!=1){ // 质因数分解 
		if(a%j == 0){
			num2[j]++;
			a =a/j;
		}
		else
			j++;
	}
	for(int i=0;i<1001;i++){
		if(num2[i]!=0){
			if(num1[i] < k)
				k = num1[i];
		}
	}
	printf("%d\n",k);
	return 0;
} 

文章来源:https://blog.csdn.net/ADDDDDDS/article/details/135756716
本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。