题目描述
给出一个正整数(n),求(lcm(1,2,...,n))对(2^{32})取模的结果
((1leq nleq 10^8)),数据组数(Tleq 10^4)
分析
把每一个数质因数分解,可以得到
(lcm(prod p_i^{b[1][i]},prod p_i^{b[2][i]},...prod p_i^{b[n][i]})=prod p_i ^{max(b[x][i])})
空间限制比较小,1e8的数据欧拉筛可能MLE,那么就用1e8/32个int来判断每一位是不是质数
还有一个常数的小优化就是%(2^{32})可以转化为&((1<<32)-1)
代码
#include<bits/stdc++.h>
#define rep(X,A,B) for(int X=A;X<=B;++X)
#define tep(X,A,B) for(int X=A;X>=B;--X)
#define LL long long
const int N=5761460;
const int M=3125010;
const int maxn=1e8;
const int MX=5;
const LL MOD=4294967296;
using namespace std;
int a[N];
unsigned int vis[M];
int p[N],cnt=0;
bool GET(int x){
return (vis[x>>MX]>>(x&((1<<MX)-1)))&1;
}
void UPD(int x){
vis[x>>MX]|=(1<<(x&((1<<MX)-1)));
}
void INIT(){
for(int i=2;i<=maxn;i++){
if(!GET(i))p[++cnt]=i;
for(int j=1;j<=cnt&&p[j]*i<=maxn;j++){
UPD(i*p[j]);
if(i%p[j]==0)break;
}
}
a[0]=1;
rep(i,1,cnt){
LL now=(1LL*a[i-1]*p[i])&(MOD-1);
a[i]=now;
}
}
void SOLVE(){
int n;
scanf("%d",&n);
int pos=upper_bound(p+1,p+cnt+1,n)-p;
LL res=a[pos-1];
for(int i=1;i<=cnt&&p[i]<=n/p[i];i++){
LL now=p[i]*p[i];
for(;now<=n;now*=p[i])res=(res*p[i])&(MOD-1);
}
printf("%lld
",res);
}
int main(){
INIT();
int T;
scanf("%d",&T);
rep(o,1,T){
printf("Case %d: ",o);
SOLVE();
}
return 0;
}