题解 | #区间合数最小公倍数#

出题人这句话理解好久,但是终于出来了,泪目.

本题需要求区间所有合数的最小公倍数，也就是需要统计区间内每个素数出现的最高的幂。

从第一个质数i开始找它的最大的一个幂j,使j的倍数出现在[l,r]内的值最大,这样的幂的积就是结果

#define ll long long
using namespace std;
const ll P=1000000007;
ll l,r,ans=1;
bool isPrime(ll a){
    if(a<2)return 0;
    for(int i=2;i*i<=a;++i)
        if(a%i==0)return 0;
    return 1;
}
int main(){
    scanf("%lld%lld",&l,&r);
    int f=0;
    for(ll i=2;i<=r;i++){
        if(i>=l&&f==0&&!isPrime(i))f=1;
        if(isPrime(i)){
            ll j=i;
            if(j*2>r)continue;
            while(r-(r%j)>=l)j*=i;
            j/=i;
            j%=P;
            ans*=j;
            ans%=P;
            //printf("%lld-%lld-%lld\n",i,j,ans);
        }
    }
    if(f)printf("%lld",ans);
    else printf("-1");
    return 0;
}