[编程题]整除问题
#include"iostream"
#define N 1001
using namespace std;
/*确定n!的质因子 数组统计质因子出现的次数
用n!除以a 实际上除以a的质因子 每除一次 数组中对应元素值-1
若小于0 则除不尽 结束循环
每一轮k++ 巧妙在于除以a 实际上除以a的质因子 表现为数组元素值-1
注：参考了题解2做法*/
int main(){
int n, a;
while(cin>> n>> a){
int counts[N], k= 0, flag= 1;// 空间换时间
for(int i= 0; i< N; i++){counts[i]= 0;}
for(int i= 2; i<= n; i++){// n的阶乘的每一项
int temp= i;
for(int k= 2; k<= i; k++){// 确定质因数
while(temp% k== 0){temp/= k; counts[k]++;}// 统计质因数
}
}
while(flag){// 能整除就整除
for(int i= 2, temp= a; i<= a; i++){
while(temp% i== 0){// 确定质因数
temp/= i; counts[i]--; // 统计质因数
if(counts[i]< 0){flag= 0;break;}// a的k次方已经整除不了n！了
}
}
if(flag){k++;}
}
cout<< k<< endl;
}
}
发表于 2022-02-18 16:15:12
回复(0)
#include<iostream>
#include<cstdio>
#include<cmath>
#include<vector>
using namespace std;
//给定n，a求最大的k，使n！可以被a^k整除但不能被a^(k+1)整除
int main() {
int n, a;
int i, j, k, ktemp, l, bound;
int resultk = 10000;
int zhiyinshu_a[1001] = { 0 };
int zhiyinshu_n[1001] = { 0 };
bool isPrime[1001];
isPrime[0] = false;
isPrime[1] = false;
for (i = 2; i <= 1000; i++) {
isPrime[i] = true;
}
for (i = 2; i < 1001; i++) {
bound = sqrt(i);
for (j = 2; j <= bound; j++) {
if (i % j == 0) {
isPrime[i] = false;
}
}
}//得到长度为1000的isPrime数组，质数位置为true
scanf("%d %d", &n, &a);
//cin >> a;
j = 2;
while (j != a) {
if (isPrime[j]) {
if (a % j == 0) {
zhiyinshu_a[j] = zhiyinshu_a[j] + 1;
a = a / j;
}
else {
j++;
}
}
else {
j++;
}
}
zhiyinshu_a[j] = zhiyinshu_a[j] + 1;//这部分是对a进行质因数分解，对应质因子的指数储存在zhiyinshu_a的相应位置中
//cin >> k;
for (k = 2; k <= n; k++) {
l = 2;
ktemp = k;
while (l != ktemp) {
if (isPrime[l]) {
if (ktemp % l == 0) {
zhiyinshu_n[l] = zhiyinshu_n[l] + 1;
ktemp = ktemp / l;
}
else {
l++;
}
}
else {
l++;
}
//cout << l << endl;
}
zhiyinshu_n[l] = zhiyinshu_n[l] + 1;
//cout <<"k:" <<k<<endl;
}//这部分将n！进行质因数分解，得到的结果及指数储存在zhiyinshu1_n的相应位置中
for (i = 2; i <= n; i++) {
if (isPrime[i]) {
if (zhiyinshu_n[i] < zhiyinshu_a[i]) {
cout << 0;
return 0;
}
else if(zhiyinshu_n[i] == zhiyinshu_a[i]){
cout << 1;
return 0;
}
else {
if (zhiyinshu_a[i] == 0) {
continue;
}
if (zhiyinshu_n[i] / zhiyinshu_a[i] < resultk) {
resultk = zhiyinshu_n[i] / zhiyinshu_a[i];
}
}
}
else{
continue;
}
}
cout << resultk;
//for (k = 0; k < 30; k++) {
// cout << k << ":" << zhiyinshu_a[k] << endl;
//}
//for (i = 0; i < 10; i++) {
// cout << i << ":" << zhiyinshu_n[i] << endl;
//}
return 0;
}
发表于 2021-04-11 21:47:37
回复(0)
#include<iostream>
#include<cstring>
#include<cmath>
using namespace std;
const int MAXLEN = 1001;
void Change(int *count,int n)
{
for(int i = 2;i <= int(sqrt(n));i++)
{
while(n % i == 0)
{
count[i]++;
n /= i;
if(n == 1) break;
}
}
if(n > 1) count[n]++;
}
int main()
{
int count1[MAXLEN],count2[MAXLEN];
memset(count1,0,MAXLEN * sizeof(int));
memset(count2,0,MAXLEN * sizeof(int));
int n,a;
cin >> n >> a;
for(int i = n;i > 1;i--)
{
Change(count1,i);
}
Change(count2,a);
int min = 0x7fffffff;
for(int i = 0;i < MAXLEN;i++)
{
if(count2[i])
{
int t = count1[i] / count2[i];
if(t < min) min = t;
}
}
cout << min;
return 0;
}
发表于 2021-01-24 19:48:21
回复(0)
//zsy大佬的思路 膜拜
//1.先用数组保存阶乘得数据,再一次次的除a,每次除尽 k++
//2.直到不能整除a 此时结束循
#include<stdio.h>
void change(int a[])//调整数组,使每位只有单位数字
{
int f=0;
for(int i=0;i<3000;i++){
int b=a[i]+f;
a[i]=b%10;
f=b/10;
}
}
int abc(int a[])//判断数组是否全部为0,即判断得到数是否等于0
{
for(int i=3000-1;i>=0;i--){
if(a[i]>0)
return i;
}
return 0;
}
int main()
{
int n,a;
scanf("%d%d",&n,&a);
int s[3000]={0};s[0]=1;
int i,j;
for(i=1;i<=n;i++)//阶乘保存在数组中每位保存一个数
{
for(j=0;j<3000;j++)//每一位都乘i
s[j]*=i;
change(s);//全乘完一个数进位处理
}
int k=0,f=0;
while(abc(s))//现在的数是否变成了0
{
for(i=3000-1;i>=0;i--)//每一位都除a
{
int b=s[i]+f*10;
s[i]=b/a;
f=b%a;//判断余数
}
if(f==0)//一次全部位除完a
k++;//余数0说明整除成功
else
break;
}
printf("%d\n",k);
}
编辑于 2020-04-20 17:38:53
回复(0)
import java.math.BigInteger;
import java.util.Scanner;
public class Main {
public static void main(String[] args)
{
int n,a;
Scanner sc = new Scanner(System.in);
while(sc.hasNext())
{
n = sc.nextInt();
a = sc.nextInt();
BigInteger num = BigInteger.ONE;
for(int i = 2;i <= n;i ++)
num = num.multiply(BigInteger.valueOf(i));
int t = 0;
BigInteger d = BigInteger.valueOf(a);
while(num.compareTo(BigInteger.ZERO) == 1 && num.mod(d).compareTo(BigInteger.ZERO) == 0)
{
t ++;
num = num.divide(d);
}
System.out.println(t);
}
}
}
发表于 2020-03-11 18:10:54
回复(0)
#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <limits>
using namespace std;
int n,a;
bool flag[1001];
vector<int> prime;
map<int,int> prime_n;
map<int,int> prime_a;
void get_prime(){//1到1000所有质数
fill(flag,flag+1001,true);
flag[0] = false;
flag[1] = false;
for(int i=2;i<=1000;i++){
if(flag[i]){
for(int j=i*i;j<=1000;j=j+i){
flag[j] = false;
}
prime.push_back(i);
}
}
}
void get_prime_n(){//n的质因数及其个数
int temp = n;
for(int i=0;i<prime.size() && prime[i]<=n;i++){
int ans=0;
while (n/prime[i])
{
n=n/prime[i];
ans +=n;
}
if(ans>0)
prime_n[prime[i]] = ans;
n=temp;
}
}
void get_prime_a(){//a的质因数及其个数
for(int i=0;i<prime.size() && prime[i]<=a;i++){
int ans=0;
while (a%prime[i]==0)
{
a=a/prime[i];
ans ++;
}
if(ans>0)
prime_a[prime[i]] = ans;
}
}
//计算结果
int calculate(){
int ans=numeric_limits<int>::max();
for(auto &e:prime_a){
ans = min(ans,prime_n[e.first]/e.second);
}
return ans;
}
int main(){
get_prime();
cin>>n>>a;
get_prime_n();
get_prime_a();
cout<<calculate()<<endl;
return 0;
} 上面大佬们的解法，重点在n的阶乘的因式分解
编辑于 2020-03-01 21:53:51
回复(0)
/*
1-n分解质因数，求每个因子出现次数，然后对a分解质因数，取两者质因子交集
然后取交集中质因子次数最小的即为结果
*/
#include <bits/stdc++.h>
#define INF 0x3f3f3f3f
using namespace std ;
set<int>s[5] ;
map<int,int>mp[5];
void get_FacPrime( int m , int id ) {
for( int i = 2 ; i * i <= m ; i++ ) {
if( ( m % i ) == 0 ) {
s[id].insert(i) ;
while( m % i == 0 ){ m /= i ; mp[id][i]++ ; }
}
}
if( m > 1 ) { s[id].insert(m) ; mp[id][m]++ ;}
}
int main() {
int n , a;
cin >> n >> a ;
for( int i = 2 ; i <= n ; i++ ) {
get_FacPrime( i , 0 );
}
int res = INF ;
get_FacPrime( a , 1 );
set_intersection(s[0].begin(),s[0].end(),s[1].begin(),s[1].end(),inserter(s[2],s[2].begin()));
for( auto i : s[2] ){
res = min( res , mp[0][i] );
}
cout << res << endl;
return 0 ;
}
编辑于 2020-03-01 12:50:05
回复(0)
先用数组保存阶乘的数据，再一次次地除以a，每次出尽后 K ++，
直到除不尽即可得到对应可以除尽的那个K值。
#include<iostream>
#include<string>
using namespace std;
void change(int a[]){ //调整数组，使每位只有单个数字，即个十百千万这样排列
int f=0;
for(int i=0;i<3000;i++){
int b=a[i]+f;
a[i]=b%10;
f=b/10;
}
}
int abc(int a[]){ //判断数组是否全部为0，即判断得到数是否等于0
for(int i=3000-1;i>=0;i--){
if(a[i]>0)
return i;
}
return 0;
}
int main(){
int n,a;
cin>>n>>a;
int s[3000]={0};s[0]=1;
for(int i=1;i<=n;i++){ //首先进行阶乘，保存在数组中，每位保存一个数
for(int j=0;j<3000;j++){
s[j]*=i;
}
change(s); //每次乘完后进行调整
}
int k=0,f=0; //分别为计数位，标志位（用来进位或者借位）
while(abc(s)){
for(int i=3000-1;i>=0;i--){ //进行除法，调整为除以a后的数
int b=s[i]+f*10;
s[i]=b/a;
f=b%a; //判断余数
}
if(f==0) //余数等于0，即除尽了，计数加一，进行下一次除法
k++;
else //否则除不尽，直接退出循环
break;
}
cout<<k;
}
编辑于 2019-03-12 19:11:43
回复(0)
#include <iostream>
using namespace std;
bool mark[1001];
int prime[1001]; //存放1~1000中的素数
int primeNum;
int cnt[1001]; //cnt[i]表示，prime[i]所保存的素数在n!中的因子数，即幂指数
int cnt2[1001]; //cnt2[i]表示，prime[i]所保存的素数在a中的因子数
void init(){ //素数筛法，找出1~1000中素数存放在prime数组中
primeNum=0;
for(int i=2;i<=1000;i++){
if(mark[i]==true) continue;
mark[i]=true;
prime[primeNum++]=i;
for(int j=i*i;j<=1000;j=j+i){
mark[j]=true;
}
}
}
int main(){
int n,a;
init();
while(cin>>n>>a){
for(int i=0;i<primeNum;i++){
cnt[i]=0;
cnt2[i]=0;
}
for(int i=0;i<primeNum;i++){ //对n！求素数prime[i]的幂指数
int temp=n;
while(temp!=0){
cnt[i]+=temp/prime[i];
temp=temp/prime[i];
}
}
int min=999999; //min是指满足a整除n!最小的倍数k
for(int i=0;i<primeNum;i++){ //对a求素数prime[i]的幂指数
while(a%prime[i]==0){
cnt2[i]++;
a=a/prime[i];
}
if(cnt2[i]==0) continue;
if(cnt[i]/cnt2[i]<min) min=cnt[i]/cnt2[i];
}
cout<<min<<endl;
}
return 0;
}
using namespace std;
bool mark[1001];
int prime[1001]; //存放1~1000中的素数
int primeNum;
int cnt[1001]; //cnt[i]表示，prime[i]所保存的素数在n!中的因子数，即幂指数
int cnt2[1001]; //cnt2[i]表示，prime[i]所保存的素数在a中的因子数
void init(){ //素数筛法，找出1~1000中素数存放在prime数组中
primeNum=0;
for(int i=2;i<=1000;i++){
if(mark[i]==true) continue;
mark[i]=true;
prime[primeNum++]=i;
for(int j=i*i;j<=1000;j=j+i){
mark[j]=true;
}
}
}
int main(){
int n,a;
init();
while(cin>>n>>a){
for(int i=0;i<primeNum;i++){
cnt[i]=0;
cnt2[i]=0;
}
for(int i=0;i<primeNum;i++){ //对n！求素数prime[i]的幂指数
int temp=n;
while(temp!=0){
cnt[i]+=temp/prime[i];
temp=temp/prime[i];
}
}
int min=999999; //min是指满足a整除n!最小的倍数k
for(int i=0;i<primeNum;i++){ //对a求素数prime[i]的幂指数
while(a%prime[i]==0){
cnt2[i]++;
a=a/prime[i];
}
if(cnt2[i]==0) continue;
if(cnt[i]/cnt2[i]<min) min=cnt[i]/cnt2[i];
}
cout<<min<<endl;
}
return 0;
}
发表于 2019-02-25 13:39:24
回复(0)
#include<stdio.h>
#include<math.h>
int prime[100000];
int primeSize = 0;
bool mark[100000] = { 0 };
int A[1010] = { 0 };
int B[1010] = { 0 };
void init() {
for (int i = 2; i <= 100000; i++) {
if (mark[i] == 0) {
prime[primeSize++] = i;
if (i <= 1000) {
for (int j = i * i; j<100000; j += i)
{
mark[j] = true;
}
}
}
}
}
int main() {
init();
int n, a;
while (scanf("%d%d", &n,&a) != EOF) {
int i = 0;
while (prime[i] <= n) {
int temp = prime[i];
while (temp<=n) {
B[i] = n / temp + B[i];
temp = temp * prime[i];
}
i++;
}//求n！的素因数
int j = 0;
while (a != 1 && j < primeSize) {
if (a%prime[j] == 0) {
A[j]++;
a /= prime[j];
}
else j++;
}//求a的素因数；
int ans=10010010;
for (; j >= 0; j--) {
if (A[j] == 0)continue;
int x = B[j] / A[j];
if (ans > x)ans = x;
}
printf("%d\n", ans);
}
return 0;
}
发表于 2018-03-06 18:18:31
回复(0)
根据王道代码改变，三个循环融合为一个循环，不仅代码量减少，而且时间复杂度也大大
降低，但是代码可读性较差。
#include <stdio.h>
#include <algorithm>
using namespace std;
int prime[1000];
int primesize = 0;
bool mark[1001];
//求1到1000的素数
void init()
{
for(int i=1; i<1001; i++)
{
mark[i] = false;//标记全为素数
}
for(int i=2; i<1001; i++)
{
if(mark[i] == true) continue;//如果不是素数，则跳过
prime[primesize++] = i;
for(int j=i*i; j<=1000; j+=i)
{
mark[j] = true;//如果是素数，则它的所有倍数，都不是素数
}
}
}
int main()
{
init();
int n,a;
int buf1[1010];
int buf2[1010];
while(scanf("%d %d", &n, &a) == 2)
{
int ans = 13412341234;
for(int i=0; i<primesize; i++)
{
buf1[i] = buf2[i] = 0;
while(a%prime[i] == 0)
{
buf2[i]++;
a = a/prime[i];
}
if(buf2[i] == 0) continue;
int t = n;
while(t)
{
buf1[i] += t/prime[i];
t = t/prime[i];
}
if(buf1[i]/buf2[i] < ans)
ans = buf1[i]/buf2[i];
}
printf("%d\n", ans);
}
return 0;
}
这是我参照王道的思路，但自己写的代码，时间复杂度是一样的
#include <stdio.h>
#include <algorithm>
using namespace std;
int prime[1000];
int primesize = 0;
bool mark[1001];//?????
//求1到1000的素数
void init()
{
for(int i=1; i<1001; i++)
{
mark[i] = false;//标记全为素数
}
for(int i=2; i<1001; i++)
{
if(mark[i] == true) continue;//如果不是素数，则跳过
prime[primesize++] = i;
for(int j=i*i; j<=1000; j+=i)
{
mark[j] = true;//如果是素数，则它的所有倍数，都不是素数
}
}
}
int main()
{
init();
int n,a;
while(scanf("%d %d", &n, &a) != EOF)
{
///求a的素因数
int a_prim[100];
int a_primSize = 0;
for(int i=0; prime[i]<=a; i++)
{
int prime1 = prime[i];
//找到a的一个素因数
if(a%prime1 == 0)
{
int acct = 0;
//a素因数的个数
while(a%prime1 == 0)
{
acct++;
a/=prime1;
}
//计数器归零
a_prim[a_primSize] = 0;
//不是素数则跳过
if(acct == 0) continue;
//求n!中对应素因数的幂指数
for(int j=2; j<=n; j++)
{
//出问题点
int t = j;
while(t%prime1 == 0)
{
a_prim[a_primSize]++;
t = t/prime1;
}
}
a_prim[a_primSize] /= acct;
a_primSize++;
}
}
sort(a_prim, a_prim+a_primSize);
printf("%d\n", a_prim[0]);
}
return 0;
}
编辑于 2018-03-15 14:56:22
回复(0)
质因子分解：整数与n!
考察：
1.素数筛
2.对n!质因子分解算法
3.对a质因子分解算法
int nFac[MAXN]={0};//记录n!的质因数分解后的结果，n!存在质因数i，则aFac[i]=指数 int aFac[MAXN]={0};//记录a的质因数分解的结果，a存在质因数i，则aFac[i]=指数
比较n！和a的相同质因数的指数相除的最小值为所求。
例如:
6!=2^4+3^2+5^1
10=2^1*5^1
有公共质因数：
2 指数相除为4/1=4
5 指数相除为1/1=1
所以答案为1
#include <cstdio>
#include <vector>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN=1010;
const int INF=(1<<31)-1;
//素数筛
bool p[MAXN]={false};//未被筛选
vector<int> prime;
void getPrime()
{
p[0]=p[1]=true;//被筛去，不是素数
for(int i=2;i<MAXN;i++)
{
if(p[i]==false)//未被筛去，是素数
{
prime.push_back(i);
for(int j=i+i;j<MAXN;j+=i)
p[j]=true;
}
}
}
int nFac[MAXN]={0};//记录n!的质因数分解后的结果，n!存在质因数i，则aFac[i]=指数
int aFac[MAXN]={0};//记录a的质因数分解的结果，a存在质因数i，则aFac[i]=指数
//对n!质因子分解
void getnFac(int n)
{
for(int i=0;prime[i]<=n;i++)
{
int pow=0;
int tempn=n;
while(n!=0)
{
pow+=n/prime[i];
n/=prime[i];
}
nFac[prime[i]]=pow;
n=tempn;//还原n
}
}
//对a质因子分解
int getaFac(int a)
{
int ans=INF;
int sqr=sqrt((double)a);
for(int i=0;prime[i]<=sqr;i++)
{
while(a%prime[i]==0)
{
aFac[prime[i]]++;
a=a/prime[i];
}
//prime[i]是a的质因子
if(aFac[prime[i]]>0)
{
//prime[i]不是n!的质因子
if(nFac[prime[i]]==0)
ans=0;
//取相同质因子的指数相除最小的
else if(nFac[prime[i]]/aFac[prime[i]]<ans)
ans=nFac[prime[i]]/aFac[prime[i]];
}
if(a==1)
break;
}
if(a!=1)
{
//剩下一个大于根号a的数是a的质因子
aFac[a]++;
//剩下一个大于根号a的数不是n!的质因子
if(nFac[a]==0)
ans=0;
//取相同质因子的指数相减最小的
else if(nFac[a]/aFac[a]<ans)
ans=nFac[a]/aFac[a];
}
return ans;
}
int main()
{
int n,a;
scanf("%d%d",&n,&a);
getPrime();
getnFac(n);
int ans=getaFac(a);
printf("%d",ans);
return 0;
}
发表于 2019-03-07 11:28:00
回复(2)
根据王道机试指南分解素因数的例题做了一定改变，大体思路不变，只是不筛选素数，增加了循环的时间复杂度，但是减少了代码量，在机试过程中这样写可能速度更快一些，提供以下参考：
#include<stdio.h>
int main(){
int a,n;
while(scanf("%d%d",&n,&a)!=EOF){
int count1[1010]={0};
int count2[1010]={0};
for(int i=2;i<=n;i++){
int t=n;
while(t){
count1[i]+=t/i;
t=t/i;
}
}
int ans=233333333;
for(int i=2;i<=a;i++){
while(a%i==0){
count2[i]++;
a/=i;
}
if(count2[i]==0) continue;
if(count1[i]/count2[i]<ans)
ans=count1[i]/count2[i];
}
printf("%d\n",ans);
}
return 0;
}
下面是筛选素数放入prime数组后再进行判断，二者均供参考
#include<stdio.h>
#define N 1010
int prime[N];
int primesize;
bool mark[N];
void init(){
for(int i=0;i<N;i++)
mark[i]=false;
for(int i=2;i<N;i++){
if(mark[i]==true) continue;
else{
prime[primesize++]=i;
for(int j=i*i;j<N;j+=i)
mark[j]=true;
}
}
}
int main(){
init();
int a,n;
while(scanf("%d%d",&n,&a)!=EOF){
int count1[N]={0};
int count2[N]={0};
for(int i=0;i<primesize;i++){
int t=n;
while(t){
count1[i]+=t/prime[i];
t/=prime[i];
}
}
int ans=233333333;
for(int i=0;i<primesize;i++){
while(a%prime[i]==0){
count2[i]++;
a/=prime[i];
}
if(count2[i]==0) continue;
if(count1[i]/count2[i]<ans)
ans=count1[i]/count2[i];
}
printf("%d\n",ans);
}
return 0;
}
编辑于 2018-01-16 16:00:54
回复(6)
#include <stdio.h>
#include <string.h>
using namespace std;
bool premiere[1001]; //检验素数
int prem[200]; //存储素数
int preNum; //素数个数
int num1[200]; //n！的质因子
int num2[200]; //a的质因子
void setPrem() {
for (int i = 2; i < 1001; i++) {
if (premiere[i]) {
continue;
}
prem[preNum++] = i;
int j = 1001 / i;
for (int k = 2; k <= j; k++) {
premiere[k*i] = 1;
}
}
}
void setNum(int n, int *num) {
for (int i = 0; i < preNum; i++) {
while (n%prem[i] == 0) {
num[i]++;
n /= prem[i];
}
}
}
int main() {
int m, a;
memset(premiere, 0, sizeof(premiere));
setPrem();
while (scanf("%d%d", &m, &a) != EOF) {
memset(num1, 0, sizeof(num1));
memset(num2, 0, sizeof(num2));
for (int i = 2; i <= m; i++)
setNum(i, num1);
setNum(a, num2);
int min = 100 * 100;
for (int i = 0; i < preNum; i++) {
if (num2[i] == 0)
continue;
if (min > num1[i] / num2[i])
min = num1[i] / num2[i];
}
printf("%d\n", min);
}
return 0;
}
发表于 2019-09-04 19:45:52
回复(0)
#分解质因数+指数不断相减
#include <iostream>
#include <vector>
#include <cmath>
using namespace std;
int x[1005];
int y[1005];
int k;
void split(int n,int *a)
{
for(int i=2;i<=sqrt(n)+1;i++){
while(n%i==0){
a[i]++;
n/=i;
}
if(n<=1) break;
}
if(n>1) a[n]++;
}
int main()
{
int n,a;
cin>>n>>a;
split(a,y);
for(int i=2;i<=n;i++)
split(i,x);
while(1){
for(int i=2;i<=max(a,n);i++){
if(y[i]>x[i]){
cout<<k<<endl;
return 0;
}
x[i]-=y[i];
}
k++;
}
}
发表于 2019-05-09 20:57:28
回复(0)
纯c
#include <stdio.h>
void pf(int prime[],int num)
{
for(int i=2; i*i<=num; i++)
{
while(num%i==0)
{
prime[i]++;
num/=i;
}
}
if(num>1)
{
prime[num]++;
}
}
int main()
{
int n,a;
while(scanf("%d%d",&n,&a)!=EOF)
{
int pn[1001]= {0};
int pa[1001]= {0};
pf(pa,a);
for(int i=2; i<=n; i++)
{
pf(pn,i);
}
int k=1000000000;
for(int i=2; i<=a; i++)
{
if(pa[i]>0 && pn[i]/pa[i]<k)
{
k=pn[i]/pa[i];
}
}
printf("%d\n",k);
}
return 0;
}
发表于 2020-02-28 23:52:08
回复(3)
#include<iostream>
#include<cmath>
#include<map>
using namespace std;
void prime_factor(int N, map<int, int> &m)//分解质因数。二元组:质因子,幂次
{
for (int j = 2; j <= sqrt(N); j++)//短除法
{
while (N % j == 0)
{
if (m[j] >= 1)
m[j]++;
else
m[j] = 1;
N = N / j;
}
if (N <= 1)//除到1，即分解完了
break;
}
if (N > 1)//本身是质数 或最后的余数是质数
if (m[N] >= 1)
m[N]++;
else
m[N] = 1;
}
int main()
{
int n, a, k;
map<int, int>::iterator index, it;
map<int, int> m_a;//map存储 质因子：幂次
map<int, int> m_n;
while (cin>>n>>a)
{
prime_factor(a, m_a);//计算a的质因子及其幂次
for (int i = 2; i <= n; i++)//计算n!的质因子及其幂次
prime_factor(i, m_n);
k = 10000;
for (it = m_a.begin(); it != m_a.end(); it++)//查找相同的质因子
{
index = m_n.find(it->first);
if (index != m_n.end())
{
int temp = index->second / it->second;
if (temp < k)
k = temp;
}
}
m_a.clear();
m_n.clear();
cout << k << endl;
}
return 0;
} 应该是最好的解法！
n！和 a 的相同质因数的幂次相除的结果中最小的为所求 k
利用map容器存储质因子和幂次，之后找相同质因子也很方便
编辑于 2020-05-06 19:01:12
回复(0)
问题信息
难度：
93条回答
315收藏
10547浏览
通过挑战的用户
查看代码-
2023-03-09 16:23:46
-
2023-03-08 17:13:33 -
2023-03-04 17:19:26
-
2023-02-15 21:29:04 -
2023-02-07 18:08:21
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
