博客

题目描述

一天，szb 在上学的路上遇到了灰太狼。

灰太狼：帮我们做出这道题就放了你。

szb：什么题？

灰太狼：求一个能被 [1,n]内所有数整除的最小数字，并对 100000007 取模。

szb：这题太水了，就让我小弟来做好了。

然后你就光荣的接受了这个任务。

输入格式

一行一个数 nnn。

输出格式

一行一个数 ans。

样例

样例输入

10

样例输出

2520

数据范围与提示

n≤10^8

​​

这个题目很水，Ans=lcm(1,,,,,n);

泽勒钱大佬出题的时候卡了一下内存，给了32MB

思路还是一样，筛一遍素数，看看大体有多少个，再计算一下内存，不要开很大。。

#include<iostream>
#include<cstdio>
#define LL long long 
#define MAXN 25000000
#define Mod 100000007
int prime[1600000],cnt;
bool is_prime[MAXN];
LL Euler(int n){
    LL res,Ans=1;
    for(register int i=2;i<=n;++i){
        if(!is_prime[i]){
            prime[++cnt]=i;
            for(res=i;res*(LL)i<=n;res*=i);
            Ans=(Ans*res)%Mod;
        }
        for(int j=1;j<=cnt&&prime[j]*i<=n;++j){
            is_prime[prime[j]*i]=true;
            if(i%prime[j]==0) break;
        }
    }
    return Ans;
}
int Main(){
    freopen("chen.in","r",stdin);
    freopen("chen.out","w",stdout);
    int n;
    scanf("%d",&n);
    long long Ans=Euler(n);
    printf("%lld\n",Ans);
    return 0;
}
int Aptal_is_My_Son=Main();
int main(int argc,char *argv[]){ ; }

本校的评测机垃圾，n<=25000000,跑了一下25000000之内大约有160W个素数，计算一下内存没问题，这还是有点良心的。。

刚开始我想f[i]表示前i个数的lcm，那么f[i]=lcm(f[i-1],i)

于是乎五分钟写了分块打表，美妙跑250W，打了十个表，然而这样的递推在取模意义下并不成立。