Python学习

九度题目1104:整除问题

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

输入:
两个整数n(2<=n<=1000),a(2<=a<=1000)
输出:
一个整数.

样例输入:
6 10

样例输出:
1

思路:
求的是最大的k使得b可以被a^k整除,但是不可以被a^(k+1)整除。用的方法是求出所有b的素因子次方,看a中相应素因子次方,若没有,调过,若有,判断b的次方是a的次方的几倍,选择所有素因子中次方倍数最小的。这样才是可以满足b可以被a整除但再多一个次方就不可以了。

代码:

#include<iostream>
#include<stdio.h>
#include<cstdio>
#include<math.h>
#define MAX 1002
using namespace std;
int a[1002];
int prime[1002];
int primeSize;
bool judge(int i) {  //是素数?
 
    if (i <= 1)
        return false;
    int bound = (int)sqrt((double)i)+1;
    for (int j = 2; j <= bound; j++) {
        if (i%j == 0)
            return false;
    }
    return true;
}
void init() {    //初始化,a[i]为1表示不是素数,a[i]为0是素数
    primeSize=2;
    for (int i = 0; i < MAX; i++) {
        a[i] = 0 ;
    }
    a[0] = 1;
    a[1] = 1;
    a[2] = 0;
    prime[1]=2;
    for (int i = 3; i <= MAX; i++) {
        if (a[i] == 1) //已经不是素数了
            continue;
        if (!judge(i)) { //不是素数
            a[i] = 1;
            if(i< (int)sqrt((double)MAX)){
                for (int j = i*i; j <= (int)sqrt((double)MAX); j += i) {
                    a[j] = 1;
                }
                 
            }       
        }
        else
            prime[primeSize++]=i;
    }
}
    int cnt[1002];  //n!中的a中所存因子数
    int cnt2[1002]; //a中的中所存因子数
int main() {
    int n,a;
    init();
    while(cin>>n>>a){
        for(int i=1;i<primeSize;i++){
            cnt[i]=cnt2[i]=0;//计数器清零
        }
        for(int i=1;i<primeSize;i++){ //将n!分解,遍历每一个0到1000的临时素数
            int t=n;  //临时保存n
            while(t){
                cnt[i]+=t/prime[i]; 
                t/=prime[i];//依次计算t/prime[i]^k,累加其值,直到t/prime[i]^k变为0
            }
        }
        int ans=123123123;  //答案初始化为一个大整数,为取最小值做准备
        for(int i=1;i<primeSize;i++){  //对a分解素因数
            while(a%prime[i]==0){
                cnt2[i]++;
                a/=prime[i];
            }
            if(cnt2[i]==0) continue;//若素数不能从a中分解到,即其对应幂指数为0,则其不影响整体性,调过
            if(cnt[i]/cnt2[i]<ans)
                ans=cnt[i]/cnt2[i]; //统计这些商的最小值
        }
        cout<<ans<<endl;
    }
    return 0;
}
/**************************************************************
    Problem: 1104
    User: WZDCJ0206
    Language: C++
    Result: Accepted
    Time:0 ms
    Memory:1548 kb
****************************************************************/
Be the First to comment.

Leave a Comment

您的电子邮箱地址不会被公开。

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据

皖ICP备2020019260号-2