P4626

· · 个人记录

题意

很显然是求lcm(1,2,3...n)。

那么我们首先看几个例子：

lcm(15,25)=75 15=3\times5 25=5 ^ 2 75=3\times5 ^ 2 lcm(18,24)=72 18=2\times3 ^ 2 24=2 ^ 3\times3 72=2 ^ 3\times3 ^ 2 lcm(6,14,21)=42 6=2\times3 14=2\times7 21=3\times7 42=2\times3\times7

求n个数的最小公倍数就是求这些数中每一个同样质因子的最大指数.

拓展：求n个数的最大公约数就是这些数中每一个同样质因子的最小指数.

证明比较复杂，与lcm定义有关，感兴趣的自己去找。

所以，正解就是线性筛+标记质数的x次方，并把他们乘起来。

细节

警示后人

非（！）的优先级是最高的，写！i%p[j]与i%p[j]==0完全不一样!

代码

#include<iostream>
#include<cstdio>
#include<cstring>
#include<bitset>
#define int long long
using namespace std;
const int mod=1e8+7;
const int MAXN=1e6+20;
bitset<99999990>vis;
int p[MAXN],cnt;
int f[MAXN];
int n,ans=1;
signed main(){
    cin>>n;
    for(int i=2;i<=n;i++){
        if(!vis[i]){
            p[++cnt]=i;
            f[cnt]=i;
            ans=ans*p[cnt]%mod;
        }
        for(int j=1;j<=cnt&&i*p[j]<=n;j++){
            vis[i*p[j]]=1;
            if(i%p[j]==0){
                if(i==f[j]){
                    f[j]*=p[j];
                    ans=ans*p[j]%mod;
                }
                break;
            }
        }
    }
    cout<<ans;
    return 0;
}

因为赛时非优先级的问题，又手搓了个暴力水过了

#include<iostream>
#include<bitset>
#include<cstdio>
#include<cmath>
#include<cstring>
#define int long long
using namespace std;
const int MAXN=6e6+10;
const int mod=1e8+7;
bitset<99999990>vis;
int n,p[MAXN],cnt=0,f[MAXN],ans=1;
int qpow(int a,int b){
    int sum=1;
    while(b){
        if(b&1)sum=sum*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return sum; 
}
signed main(){
    cin>>n;
    for(int i=2;i<=n;i++){
        if(!vis[i])p[++cnt]=i;
        for(int j=1;j<=cnt&&p[j]*i<=n;j++){
            vis[p[j]*i]=1;
            if(i%p[j]==0)break; 
        }
    }
    for(int i=1;i<=cnt;i++){
        int x=log(n)/log(p[i]);
    //  cout<<x<<" ";
        ans=ans*qpow(p[i],x)%mod;
    }
    cout<<ans;
    return 0;
}