题目链接：http://lightoj.com/volume_showproblem.php?problem=1289
题意：求LCM(1, 2, 3, ... , n)%(1<<32), (1<n<=1e8);
LCM(1, 2, 3, ... , n) = n以内所有素数的最高次幂之积，例如15: 23*32*5*7*11*13 = 36360360;
为了防止TLE所以，要有一个数组表示前缀积，但是直接开LL会MLE是，因为有个%1<<32刚好是unsigned int之内，可以开int的数组；
关于求1e8内的素数表，用bool类型也会MLE的，所以可以使用bitset类型;
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <bitset>
#include <iostream>
#include <time.h> typedef long long LL; using namespace std; const int N = 1e8+;
const double eps = 1e-;
const int INF = 0x3f3f3f3f;
const LL mod = (1ll<<); int k, p[];
unsigned int Mul[];
bitset<N> f; void Init()
{
f.reset();
for(int i=; i<N; i++)
{
if(f[i]) continue;
p[k++] = i;
for(int j=i+i; j<N; j+=i)
f[j] = ;
}
} int main()
{
int T, t = ;
scanf("%d", &T); Init(); Mul[] = p[];
for(int i=; i<k; i++)
Mul[i] = Mul[i-]*p[i]; while(T --)
{
int n; scanf("%d", &n); int pos = upper_bound(p, p+k, n)-p - ; LL ans = Mul[pos]; for(int i=; i<k && (LL)p[i]*p[i]<=n; i++)
{
LL num = ;
while(num <= n)
num *= p[i];
if(num%(p[i]*p[i]) == ) num /= (p[i]*p[i]);
ans = ans*num%mod;
} printf("Case %d: %lld\n", t++, ans);
}
return ;
}
还有一种比较快一点的方法：
#include <stdio.h>
#include <string.h>
#include <math.h>
#include <algorithm>
#include <bitset>
#include <iostream>
#include <time.h> typedef long long LL; using namespace std; const int N = 1e8+;
const double eps = 1e-;
const int INF = 0x3f3f3f3f;
const LL mod = (1ll<<); int k = , p[], f[N/+];
unsigned int Mul[]; void Init()
{
p[k++] = ;
for(int i=; i<N; i+=)
{
if(f[i/]&(<<((i/)%)))
continue;
p[k++] = i;
for(int j=*i; j<N; j+=*i)
f[j/] |= (<<((j/)%));
}
///printf("%d\n", k);
} int main()
{
int T, t = ;
scanf("%d", &T); Init(); Mul[] = p[];
for(int i=; i<k; i++)
Mul[i] = Mul[i-]*p[i]; while(T --)
{
int n; scanf("%d", &n); int pos = upper_bound(p, p+k, n)-p - ; LL ans = Mul[pos]; for(int i=; i<k && (LL)p[i]*p[i]<=n; i++)
{
LL num = ;
while(num <= n)
num *= p[i];
if(num%(p[i]*p[i]) == ) num /= (p[i]*p[i]);
ans = ans*num%mod;
} printf("Case %d: %lld\n", t++, ans);
}
return ;
}