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整除但再多一个次方就不可以了。

代码:

Be the First to comment.

Leave a Comment

电子邮件地址不会被公开。 必填项已用*标注