[52]整除-京东2018秋

1.题目描述

牛牛对整除非常感兴趣。牛牛的老师给他布置了一道题:牛牛的老师给出一个n,然后牛牛需要回答出能被1到n之间(包括1和n)所有整数整除的最小的数。牛牛犯了难,希望你能编程帮他解决这个问题。

• 输入描述:
  输入包括一个整数n(1≤n ≤100000)
• 输出描述:
  输出一个整数, 即满足要求的最小整数。答案可能很大,请输出这个整数对于987654321取模的结果
• 输入示例:

  3
  

• 输出示例:

  6
  

2.题目解析

本质是找1~n的最小公倍数， 求每个素因子的最大个数相乘即可。
例：输入10 求出每个因子需要相乘的最大个数

1	2	3	4	5	6	7	8	9	10
0	3	2	0	1	0	1	0	0	0

2*2*2*3*3*5*7=2520

3.参考答案

#include <cstdio>
using namespace std;
const long mod=987654321;
int main() {
    int n;
    scanf("%d",&n);
    int tmp[n+1]; // 下标0不使用
    for(int i=1;i<=n;i++){
        // 求解i的素因子
        int k=i;
        for(int j=2;j*j<=n;j++){
            int s=0;
            while(k%j==0){//统计因子j的个数
                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=1;i<=n;i++){// 遍历所有因子
        for(int j=0;j<tmp[i];j++){ // 将每个素因子的最大个数相乘
            res=res*i%mod;
        }
    }
    printf("%lld\n",res);
    return 0;
}

https://blog.csdn.net/behboyhiex/article/details/82288326