KIDx的解题报告
题意:求n个数的最小公倍数,结果很大,得用高精度
题目链接:http://lightoj.com/volume_showproblem.php?problem=1024
找出每个数的素因子p,p必为最小公倍数的因子,最小公倍数中p的个数就是每个数的p的个数的最大值,最后,最小公倍数的因子及其个数都知道了,用高精度乘起来就是结果了,我这里用的是10000进制计算
#include <iostream>
#include <fstream>
#include <algorithm>
#include <string>
#include <set>
//#include <map>
#include <queue>
#include <utility>
#include <iomanip>
#include <stack>
#include <list>
#include <vector>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <ctime>
#include <ctype.h>
using namespace std;
#define M 1305
int res[M], p[M], cnt[10005], fac[M];
bool hash[10005];
int main ()
{
int i, j, t, n, k = 0, x, w, cc = 1, m;
/*****************素数打表*****************/
for (i = 2; i < 10001; i++)
{
if (!hash[i])
{
p[k++] = i;
for (j = i << 1; j < 10001; j+=i)
if (!hash[j])
hash[j] = true;
}
}
/*****************素数打表*****************/
scanf ("%d", &t);
while (t--)
{
scanf ("%d", &n);
memset (cnt, 0, sizeof(cnt));
int id = 0;
while (n--)
{
scanf ("%d", &x);
for (i = 0; i < k && p[i] <= x; i++)
{
int tp = 0;
while (x % p[i] == 0)
tp++, x /= p[i];
if (tp > cnt[p[i]])
{
if (cnt[p[i]] == 0) fac[id++] = p[i];//记录最小公倍数中的素因子
cnt[p[i]] = tp; //记录素因子p[i]的最大个数
}
}
}
m = 1; //初始时res的位数
w = 0; //进位
memset (res, 0, sizeof(res));
res[0] = 1; //初始时res是1
for (i = 0; i < id; i++)
{
for (j = 0; j < cnt[fac[i]]; j++)
{ //最小公倍数中一共有cnt[fac[i]]个fac[i]因子,所以要乘cnt[fac[i]]次
for (x = 0; x < m; x++) //按位相乘
{
res[x] = res[x] * fac[i] + w;
w = 0; //进位用过以后记得清0
if (res[x] >= 10000)
w = res[x] / 10000, res[x] %= 10000;
}
while (w > 0)
res[m++] = w % 10000, w /= 10000;
}
}
printf ("Case %d: %d", cc++, res[m-1]);
//因为是第一个数,不用补足4位,因为不能有前导0
for (i = m - 2; i >= 0; i--)
printf ("%04d", res[i]);
//用的一万进制,中间部分的数要补足4位
printf ("\n");
}
return 0;
}
分享到:
相关推荐
初等数论中最大公约数、最小公倍数(递归实现)程序初等数论中最大公约数、最小公倍数(递归实现)程序初等数论中最大公约数、最小公倍数(递归实现)程序
算法-数论- 最大公约数与最小公倍数.rar
求多个数的最大公约数,最小公倍数以及hanks博士son问题,数论问题
初等数论第一章第5节最小公倍数.ppt
本ppt用于,数论基础授课,整体内容较为基础,ppt内容包括:素数筛、组合排列、最大公因数最小公倍数(gcd、lcm)等知识的讲解,以及模板代码,内容涵盖较为广泛,例题较为基础,并都有答案给出。后续还给出了三道...
4最小公倍数——小学生ppt学习课件
严士健编)第一章的5个小节的练习答案:①整除的概念*带余除法,②最大公因数与辗转相除法,③整除的进一步性质及最小公倍数,④素数*算术基本定理,⑤函数[x], {x}及其在数论中的一个应用。
《数论中未解决的问题》B24的研究简报(II) ——无一能是另外两个数的倍数的集合的构造与计数,王积社,,《数论中未解决的问题》一书中的问题B24是匈牙利著名数学家Paul Erdös提出的一个组合数论问题,首先其核心是...
初等数论中输出由数查出对应位置的指标的数的表的程序初等数论中输出由数查出对应位置的指标的数的表的程序初等数论中输出由数查出对应位置的指标的数的表的程序初等数论中输出由数查出对应位置的指标的数的表的程序...
初等数论中求欧拉函数值程序初等数论中求欧拉函数值程序初等数论中求欧拉函数值程序初等数论中求欧拉函数值程序初等数论中求欧拉函数值程序初等数论中求欧拉函数值程序
数论
1.4最小公倍数 1.5算术基本定理 第2章同余 2.1同余的基本性质 2.2计算星期几 2.3循环比赛 第3章简单密码 3.1仿射加密 3.2矩阵加密 第4章剩余系 4.1完全剩余系 4.2简化剩余系 4.3Euler定理,Fermat定理 ...
算法大全(C,C++) ...2.求两数的最小公倍数 function lcm(a,b:integer):integer; begin if a(a,b); lcm:=a; while lcm mod b>0 do inc(lcm,a); end; 3.素数的求法 A.小范围内判断一个数是否为质数:
初等数论中输出1000以内的指数和最小原根表的程序初等数论中输出1000以内的指数和最小原根表的程序初等数论中输出1000以内的指数和最小原根表的程序初等数论中输出1000以内的指数和最小原根表的程序
学而思教研部蚂蚁制作 实现对大数的分解因数 求出两个数的最大公约数和最小公倍数
哈代数论本书是数论领域的一部传世名著,成书于作者在牛津大学、剑桥大学等学校授课的讲义。书中从各个不同角度对数论进行了阐述,内容包括素数、无理数、同余、费马定理、连分数、不定式、二次域、算术函数、分化等...
希尔伯特1897年向德国数学会提交的《数论报告》用新的统一的观点,将以往代数数论的知识熔为一个整体。他抓住了互反律这个中心,利用范数剩余记号将高斯古典互反律表示成简单优美的形式: ,从而猜测到高斯互反律的...
这是一个初步介绍数论知识的课件 这是一个真正数论的开始
1.1最大公约数与最小公倍数 1.2有关素数的算法 1.3方程ax+by=c的整数解及应用 1.4 求a^b mod n 第二章 高精度计算 2.1高精度加法 2.2高精度减法 2.3高精度乘法 2.4 高精度除法 练习 第三章 排列与组合 3.1加法原理与...