京东2018秋招笔试题之整除
题目描述
牛牛对整除非常感兴趣。牛牛的老师给他布置了一道题：牛牛的老师给出一个n,然后牛牛需要回答出能被1到n之间（包括1和n）所有整数整除的最小的数。牛牛犯了难，希望你能编程帮他解决这个问题。
输入描述
输入包括一个整数n(1<=n<=100000)
输出描述
输出一个整数，即满足要求的最小整数。答案可能很大，请输出这个整数对于987654321取模的结果
输入示例
3
输出示例
6
参考答案：
#define _CRT_SECURE_NO_DEPRECATE
#include<iostream>
#include<algorithm>
#include<stdlib.h>
#include<iostream>
#include<algorithm>
#include<stdlib.h>
using namespace std;
const int mod = 987654321;
const int maxn = 1e5 + 5;
int tmp[maxn];
int n;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int k = i;
for (int j = 2; j*j <= n; j++) {
int s = 0;
while (k%j == 0) {
s++;
k /= j;
}
tmp[j] = max(tmp[j], s);
}
if (k > 1)
tmp[k] = max(tmp[k], 1);
}
long long res = 1;
for (int i = 0; i <= 100000; i++) {
for (int j = 0; j < tmp[i]; j++)
res = res * i%mod;
}
printf("%lld", res);
return 0;
}
const int mod = 987654321;
const int maxn = 1e5 + 5;
int tmp[maxn];
int n;
int main() {
scanf("%d", &n);
for (int i = 1; i <= n; i++) {
int k = i;
for (int j = 2; j*j <= n; j++) {
int s = 0;
while (k%j == 0) {
s++;
k /= j;
}
tmp[j] = max(tmp[j], s);
}
if (k > 1)
tmp[k] = max(tmp[k], 1);
}
long long res = 1;
for (int i = 0; i <= 100000; i++) {
for (int j = 0; j < tmp[i]; j++)
res = res * i%mod;
}
printf("%lld", res);
return 0;
}
#京东##秋招##笔试题目#
拼多多集团-PDD公司福利 470人发布
