2018秋招 京东笔试-整除

题目：整除

能被1和n之间所有正整数整除的最小的数

输入：n

输出：输出一个整数，对987654321取模

分析：

本质是找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
#include <bits/stdc++.h> #include <iostream> using namespace std; const long
mod=987654321; const int maxn=1e5+5; int main() { int n; cin>>n; int tmp[maxn];
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){//求需要乘因子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; } }
cout << res; return 0; }
 

 

• « 上一篇：技术管理如何做？
• » 下一篇：Idea破解，亲测有效2019年5月5日