lightoj-1289(数论+素数打表)

Bertha 。 2022-06-10 10:18 215阅读 0赞

Given an integer **n**, you have to find

**lcm(1, 2, 3, ..., n)**

**lcm** means least common multiple. For example lcm(2, 5, 4) = 20, lcm(3, 9) = 9, lcm(6, 8, 12) = 24.

InputInput starts with an integer **T (≤ 10000)**, denoting the number of test cases.Each case starts with a line containing an integer **n (2 ≤ n ≤ 108)**.

OutputFor each case, print the case number and **lcm(1, 2, 3, ..., n)**. As the result can be very big, print the result modulo **232**.

For each case, print the case number and **lcm(1, 2, 3, ..., n)**. As the result can be very big, print the result modulo**232**.

Sample Input5

200

Sample Output

Case 1: 2520

Case 2: 60

Case 3: 2300527488

Case 4: 360360

Case 5: 232792560

题目题意：就是让我们求lcm(1,2,,,,n).

题目分析: 这里我们求得时候肯定不能暴力求，肯定超时，这里我们要用到一个结论:

lcm(1,2,,,,,,n+1)=lcm(1,2,,,,,,,n)\*p   （这里的p是指素数，n+1=p^k ,如果n+1可以写成这样的形式，那么就得到那样的递推式)

=lcm(1,,2,,n)      others

这个题目还要用到素数的打表的另一种写法，用位图（我表示不是很懂，但是它的两个函数给出后，就可以与以前的标记数组vis一样用了）

代码如下:

#include<iostream>
    #include<cstdio>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #define SHIFT 5
    #define ll long long
    using namespace std;
    
    ll inf;
    const int maxn=1e8+2;
    int prime[6000000+10],cnt;
    unsigned int sum[6000000+10];
    unsigned int vis[maxn>>SHIFT];
    
    void SetBit(int x){
        vis[x>>SHIFT]|=1<<(x&((1<<SHIFT)-1));
    }
    bool GetBit(int x){
        return vis[x>>SHIFT]&(1<<(x&((1<<SHIFT)-1)));
    }
    void get_prime()
    {
        for (int i=2;i<maxn;i++) {
            if (!GetBit(i)) prime[cnt++]=i;//这里就相当于vis[i]
        for (int j=0;j<cnt&&i*prime[j]<maxn;j++) {
             SetBit(i*prime[j]);//相当于vis[i*prime[j]]=false
            if (i%prime[j]==0) break;
        }
       }
    }
    void init()//把质数先乘起来，因为质数肯定满足
    {
        sum[0]=prime[0];
        for (int i=1;i<cnt;i++)
            sum[i]=sum[i-1]*prime[i];
    }
    unsigned int solve(int n)
    {
        int x=upper_bound(prime,prime+cnt,n)-prime-1;//找到n或者比它小一点的位置
        unsigned int ans=sum[x];
        for (int i=0;i<cnt&&prime[i]*prime[i]<=n;i++) {
            int cur=prime[i];
            int temp=prime[i]*prime[i];
            while (temp/cur==prime[i]&&temp<=n) {//找到每一个质数prime[i]，它在n之内有多少个prime[i]^k，有一个就得乘一个prime[i]
                cur*=prime[i];
                temp*=prime[i];
            }
            ans=ans*(cur/prime[i]);
        }
        return ans;
    }
    int main()
    {
    	get_prime();
    	init();
    	inf=pow(2,32);
    	int t;
    	scanf("%d",&t);
    	for (int icase=1;icase<=t;icase++) {
            int n;
            scanf("%d",&n);
    		printf("Case %d: %u\n",icase,solve(n)%inf);
    	}
    	return 0;
    }