Given an integer n, you have to find
lcm(1, 2, 3, ..., n)
lcm means least common multiple. For example lcm(2, 5, 4) = 20, lcm(3, 9) = 9, lcm(6, 8, 12) = 24.
Input starts with an integer T (≤ 10000), denoting the number of test cases.
Each case starts with a line containing an integer n (2 ≤ n ≤ 108).
For each case, print the case number and lcm(1, 2, 3, ..., n). As the result can be very big, print the result modulo 232.
Sample Input |
Output for Sample Input |
|
5 10 5 200 15 20 |
Case 1: 2520 Case 2: 60 Case 3: 2300527488 Case 4: 360360 Case 5: 232792560 |
Solution:
首先,lcm(1,2,...,n)为2k1*3k2*...*pxkx,pi为小于等于n的质数,piki<=n且pi(ki+1)>n
所以,先预处理出1e8范围内的质数,及其前缀积.
设pro[i]为∏p[j](1<=j<=i)
ans=1;
for(i=1;i<=31;++i)
{
找到p[j]i<=n且p[j+1]i>n;
ans*=pro[j];
}
Code:
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cmath>
#include<cstring>
#include<bitset>
using namespace std;
#define uint unsigned int
#define ull unsigned long long
const uint MAXN=1e8;
const uint MAXTOT=5761455;
const uint MAXPOW=31;
const uint INF=0xffffffff;
uint t,CASE;
bitset<MAXN+10> vis;
uint p[MAXTOT+10],tot;
uint pro[MAXTOT+10];
void GetP()
{
for(uint i=2;i<=MAXN;++i)
{
if(!vis[i])p[++tot]=i;
for(uint j=1;j<=tot&&(ull)p[j]*i<=MAXN;++j)
{
vis[p[j]*i]=true;
if(i%p[j]==0)break;
}
}
}
uint QuickPow(uint x,uint y)
{
ull res=1;
while(y--)
{
res*=x;
if(res>INF)return INF;
}
return res;
}
void init()
{
GetP();
pro[0]=1;
for(uint i=1;i<=tot;++i)pro[i]=pro[i-1]*p[i];
}
uint n;
int main()
{
init();
scanf("%u",&t);
while(t--)
{
scanf("%u",&n);
uint res=1;
for(uint i=1;i<=MAXPOW;++i)
{
uint left=0,mid,right=MAXTOT,r=0;
while(left<=right)
{
mid=(left+right)>>1;
if(QuickPow(p[mid],i)<=n)
{
r=mid;
left=mid+1;
}
else right=mid-1;
}
res*=pro[r];
}
printf("Case %d: %u\n",++CASE,res);
}
return 0;
}
原文：http://www.cnblogs.com/DOlaBMOon/p/7324846.html