ACdream 1732

input

样例个数T <=10000

每个样例一个n(2<=n<=10^8)

output

lcm(1,2,...,n)%2^32

Sample Input

Sample Output

2520
60
2300527488
360360
232792560

做法：质因分解，每个不大于n的质数不大于n的最高次幂相乘结果即为lcm(1,2,...,n)的结果

  1 #include <bits/stdc++.h>
  2 #define MAX 10000
  3 #define INF 100000000
  4 #define LL long long
  5 #define U unsigned
  6 using namespace std;
  7 int cas=1,T;
  8 U int prime[6000000],pn,*r,rn,*rr,n,*rrp;
  9 struct node
 10 {
 11     U int x,y;
 12     bool operator<(const node&a)const
 13     {
 14         return x>a.x;
 15     }
 16 };
 17 /*void init()        //TLE
 18 {
 19     pn=1;
 20     bool *vis=new bool[INF+10];
 21     priority_queue<node>q;
 22     for(int i=2;i<=MAX;i++)
 23         if(!vis[i])
 24         {
 25             for(int j=i*i;j<=INF;j+=i) vis[j]=1;
 26             q.push(node{i,i});
 27         }
 28     prime[0]=1;
 29     for(U int i=MAX+1,x=1;i<=INF;i++)
 30     {
 31         if(!vis[i]) prime[pn++]=i;
 32     }
 33     prime[pn++]=INF+10;
 34     delete []vis;
 35     r=new U int[pn+10];
 36     r[0]=1;
 37     for(int i=1;i<pn;i++) r[i]=r[i-1]*prime[i];
 38     U int res=1;
 39     rr=new U int[3000];
 40     rrp=new U int[3000];
 41     rr[0]=rrp[0]=1;
 42     rn=1;
 43     while(!q.empty())
 44     {
 45         node u=q.top();q.pop();
 46         rrp[rn]=u.x;
 47         rr[rn++]=res*u.y;
 48         if((U LL)u.x*u.y<=INF) q.push(node{u.x*u.y,u.y});
 49     }
 50     rrp[rn++]=INF+10;
 51     for(int i=1;i<rn;i++) rr[i]=rr[i-1]*rr[i];
 52 }
 53 */
 54 void init()            //最大数为10000^2，则大于10000的素数最小公倍数的最大次幂为1，小于一万时不定
 55 {
 56     bool *vis=new bool[INF+10];
 57     pn=0;
 58     for(U int i=2;i<=INF;i++)        //O(n)筛法
 59     {
 60         if(!vis[i]) prime[pn++]=i;
 61         for(U int j=0;j<pn&&i*prime[j]<=INF;j++)
 62         {
 63             vis[i*prime[j]]=1;
 64             if(i%prime[j]==0) break;
 65         }
 66     }
 67     delete []vis;            //内存不足，用完即删
 68     priority_queue<node>q;
 69     r=new U int[pn];
 70     for(int i=0;i<pn;i++)            //prime存质数，r存第i个质数对应的结果（还没算1~10000的部分）
 71     {
 72         if(prime[i]<=MAX) { r[i]=1;q.push(node{prime[i],prime[i]}); }
 73         else r[i]=r[i-1]*prime[i];
 74     }
 75     U int res=1;
 76     rr=new U int[3000];
 77     rrp=new U int[3000];
 78     rr[0]=rrp[0]=1;
 79     rn=1;
 80     while(!q.empty())            //rr存质数的幂次升序，rrp存底数
 81     {
 82         node u=q.top();q.pop();
 83         rrp[rn]=u.x;
 84         rr[rn++]=res*u.y;
 85         if((U LL)u.x*u.y<=INF) q.push(node{u.x*u.y,u.y});
 86     }
 87     rrp[rn++]=INF+10;
 88     for(int i=1;i<rn;i++) rr[i]=rr[i-1]*rr[i];        //将rrp乘起来作为1~10000的结果
 89 }
 90 int main()
 91 {
 92     //printf("%d
",sizeof(vis)+sizeof(prime));
 93     init();
 94 //    for(int i=0;i<rn;i++) printf("%u %u
",rrp[i],rr[i]);
 95     //freopen("1.in","w",stdout);
 96     //freopen("1.in","r",stdin);
 97     //freopen("1.out","w",stdout);
 98     //printf("time=%.3lf",(double)clock()/CLOCKS_PER_SEC);
 99     scanf("%d",&T);
100     while(T--)
101     {
102         scanf("%u",&n);
103         int i1=upper_bound(prime,prime+pn,n)-1-prime;        //查找>10000的结果
104         int i2=upper_bound(rrp,rrp+rn,n)-1-rrp;                //查找1~10000的结果
105         printf("%u
",r[i1] * rr[i2]);
106     }
107     delete []r;
108     delete []rrp;
109     delete []rr;
110     return 0;
111 }

View Code