LCM from 1 to n-白红宇

LCM from 1 to n

阅读量：4701 次

发布时间：2019-06-09

本文共 1668 字，大约阅读时间需要 5 分钟。

连接：

若n+1不是质数的完全平方，则可将质因数分解成p1^a1*p2^a2*……pn^an，对于每个pi^ai，显然＜n，且两两互质，所以p1^a1*p2^a2*……pn^an|L(n)，所以n+1|L(n)，L(n +1)=L(n)

若n+1是质数的完全平方，则n+1=p^k，p^k不整除1….n，p^k不整除L(n)，因为p^(k-1)|L(n)，所以p^(k-1)*p|L(n)*p，所以L(n+1)=L(n)*p。

筛法求素数时用位图压缩节省空间。

预处理出素数后然后再处理出一个前缀积，然后从小到大枚举幂次，通过二分查找该幂次下最大的素数是多少，每次答案乘上这个前缀和即可。

unsigned int 自动对2^32取模

#include
     
      #include
      
       #include
       
        #include
        
         #include
         
          #include
          
           #include
           
            #include
            #include
             
              #include
              
               #define int unsigned int#define inf 0x3f3f3f3f#define mem(a,b) memset(a,b,sizeof(a))#define ll long long#define sd(x) scanf("%d",&(x))#define sl(x) scanf("%lld",&(x))#define slf(x) scanf("%lf",&(x))#define scs(s) scanf("%s",s)#define rep(i,a,b) for(int i=a;i<=b;i++)#define per(i,a,b) for(int i=a;i>=b;i--)#define lowbit(x) x&(-x)#define ls now<<1#define rs now<<1|1#define lson l,mid,ls#define rson mid+1,r,rsusing namespace std;const int maxn=6e6+10;bitset<100000010> is_prime; int ans,sum[maxn]; int prime[maxn],tot=0;void oula(){ is_prime[1]=is_prime[0]=1; rep(i,2,1e8) { if(!is_prime[i]) prime[++tot]=i; for(int j=1;j<=tot&&i*prime[j]<=1e8;j++) { is_prime[i*prime[j]]=1; if(i%prime[j]==0) break; } }}#undef intint main(){#define int unsigned int oula(); sum[0]=1; rep(i,1,tot) sum[i]=sum[i-1]*prime[i]; int t,n; scanf("%u",&t); for(int mun=1;mun<=t;mun++) { scanf("%u",&n); ans=1; int cnt=1; while(1) { int m=(int)pow(n+0.9,1.0/cnt); if(m<2) break; int i=lower_bound(prime+1,prime+1+tot,m)-prime; if(prime[i]!=m)i--; ans*=sum[i]; cnt++; } printf("Case %u: %u\n",mun,ans); } return 0;}