文章目录

• 题目链接：
• 手写位图：
• 用bitset

题目链接：

https://vjudge.net/contest/269935#problem
直接求lcm途中的答案会很大，而且不能直接取模
以前就只知道两个数的lcm怎么求，但是多个数怎么办呢？以为也是除以他们的gcd就行了，结果不对，自己推也没有推出来，网上看了大佬们的想法才知道，是要找每个质因子最高次的 比如说2 4 6，这三个数的lcm=12，gcd=2
直接246/gcd是不等于12的 这三个数阔以写成$2^1,2^2,2^13^1$
2这个质因子的最高次是2
3这个质因子的最高次是1
因此最后的答案应该是$2^23^1=12$这样来的 然后就是这道题了，因为一个数n的质因子肯定是小于$sqrt{n}$的，所以枚举只用枚举到1e4， 然后就是筛质数那里，用到了啥位图，看懂了之后其实就是把每一位都用起来了，而stl里面有个bitset就是操作位的，好像原理就是位图这么个原理 我用clock()测一下时间，发现筛质数那里手写的位图要2000+ms，而bitset的要4000+ms
但oj上手写的AC时间是1736ms，bitset是1611ms ？？？
这是什么鬼啊？是oj有优化啥的嘛？还是我电脑太歪啦

手写位图：

#include"bits/stdc++.h" using namespace std; typedef long long LL; typedef unsigned int uint; const int maxn=1e8+5; //clock_t t1,t2; uint vis[maxn/32+50]; uint prime[6000000],sum[6000000];//质数，质数乘积前缀 void Set(int i) { int x=i/32,y=i%32; vis[x]|=((uint)1)<<y; } int Get(int i) { int x=i/32,y=i%32; return vis[x]&((uint)1<<y); } int cnt=0; void PHI(int n) { // t1=clock(); for(int i=2; i<=n; i++) { if(Get(i)==0)prime[cnt++]=i; for(int j=0; j<cnt&&(LL)i*prime[j]<=n; j++) { Set(i*prime[j]); if(i%prime[j]==0)break; } } // t2=clock(); sum[0]=prime[0]; for(int i=1; i<cnt; i++)sum[i]=sum[i-1]*prime[i]; } uint solve(LL n) { int pos=upper_bound(prime,prime+cnt,n)-prime-1;//找比n小的质数 uint ans=sum[pos]; for(int i=0; i<cnt&&(LL)prime[i]*prime[i]<=n; i++) { LL tp=prime[i]; while(tp*prime[i]<=n)tp*=prime[i]; ans*=tp/prime[i]; } return ans; } int main() { PHI(maxn-5); // cout<<"t2-t1="< int T; cin>>T; for(int Case=1; Case<=T; Case++) { LL N; cin>>N; cout<<"Case "<<Case<<": "<<solve(N)<<endl; } }

用bitset

#include"bits/stdc++.h" using namespace std; typedef long long LL; typedef unsigned int uint; const int maxn=1e8+5; //clock_t t1,t2; bitset<maxn> bt; uint prime[6000000],sum[6000000];//质数，质数乘积前缀 int cnt=0; void PHI(int n) { // t1=clock(); bt.flip(); for(int i=2; i<=n; i++) { if(bt[i])prime[cnt++]=i; for(int j=0; j<cnt&&(LL)i*prime[j]<=n; j++) { bt[i*prime[j]]=0; if(i%prime[j]==0)break; } } // t2=clock(); sum[0]=prime[0]; for(int i=1; i<cnt; i++)sum[i]=sum[i-1]*prime[i]; } uint solve(LL n) { int pos=upper_bound(prime,prime+cnt,n)-prime-1;//找比n小的质数 uint ans=sum[pos]; for(int i=0; i<cnt&&(LL)prime[i]*prime[i]<=n; i++) { LL tp=prime[i]; while(tp*prime[i]<=n)tp*=prime[i]; ans*=tp/prime[i]; } return ans; } int main() { PHI(maxn-5); // cout<<"t2-t1="< int T; cin>>T; for(int Case=1; Case<=T; Case++) { LL N; cin>>N; cout<<"Case "<<Case<<": "<<solve(N)<<endl; } }