/*
* [题意]
* 判断n!是否能被m整除(n!/m = 整数)
*
* [解题方法]
* 对m分解素因子,得出每个素因子的个数
* 若某个素因子个数大于n!中此因子的个数,则不可整除
*/
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
using namespace std;
#define LL long long
#define M 100000
#define inf 0x3fffffff
int p[9600], vis[M], k;
int cal (int f, int x) //计算f!中有多少个x因子
{
int res = 0;
while (f) {
f /= x;
res += f;
}
return res;
}
bool judge(int n, int m)
{
int i;
for (i = 0; i < k && (LL)p[i]*p[i] <= m; i++)
{
if (m % p[i] == 0)
{
int tp = 0;
do
m /= p[i], ++tp;
while (m % p[i] == 0);
if (cal(n, p[i]) < tp) return false;
}
}
if (m > 1 && n < m) return false;
return true;
}
int main()
{
int i, j, n, m;
k = 0;
for (i = 2; i < M; i++)
{
if (!vis[i])
{
p[k++] = i;
for (j = i+i; j < M; j+=i)
vis[j] = 1;
}
}
while (cin >> n >> m)
{
if (judge(n, m)) printf ("%d divides %d!\n", m, n);
else printf ("%d does not divide %d!\n", m, n);
}
return 0;
}
分享到:
相关推荐
uva272
有uva刘汝佳文件夹的50道题解,从数据结构开始,以后慢慢上传
UVa在我看来是比较全的一个题解,希望能帮助大家。欢迎下载。
UVA109的题解,经测试完全正确,还附有题解。
包含UVA在线OJ系统的绝大部分的示例代码,并都已AC,可在刷题时参考
uva最全ac代码
1.Uva_base的编译 在编译球队时,则需要在当前球队文件夹下打开终端输入执行以下命令(以下命令都是在root下执行的): ./configure make clean make 如果运行Uva_base后,出现球员越界或掉线的情况,就重新...
uva531最长公共子序列问题水题,应用简单的dp即可ac有更快速的方法欢迎讨论
这是一支完整的uva球队,包含所有基本模块,初者可在上修改得到自己的球队
UVA 题目,不是很难,试试吧
uva357的栈实现版本
《算法竞赛入门经典》UVa配套题目pdf版完整
uva10755 ac 代码,可以随意更改下载
世界著名大学UVA OJ平台上的题目部分分类,分的不好请原谅。
开源项目-codingsince1985-UVa.zip,Been solving UVa Online Judge Problems in Golang for one year (and counting)
uva_trilearn2002 源代码
这里面全部为在Uva Online Judge上面的部分题目的解答,里面提供了解答使用的源代码。
主要是uvaoj习题相关题目 练习题目
UVA 499 Solution in C/ C++
算法竞赛入门经典(第二版)的习题都是UVa上的, 但是UVa太慢了太慢了太慢了太慢了太慢了, 于是我把各章习题的pdf一次性打包下载到本地, 和大家分享:)