聊天软件是怎么开发的/网站seo设置是什么意思

原题链接 

因为有3e4个数据，如果用欧几里得算法求所有合数的最小公倍数会爆longlong

由于任意数都是最小质因数的指数的乘积。所以最小公倍数其实是[l,r]这个范围内的所有合数构成的每个质因数的最大指数的乘积。

也就是说[l,r]范围内所有质因数的最高次幂的乘积

因为，我们可以得出，最大公因数就是所有合数共同的最小次幂的乘积

代码如下

#include <iostream>
#include <algorithm>
using namespace std;
const int N=3e5+10;
const int mod=1e9+7;
int primes[N];
int cnt;
bool st[N];
int f[N];
void init(int n)
{for(int i=2;i<=n;i++){if(!st[i]) primes[cnt++]=i;for(int j=0;primes[j]<=n/i;j++){st[primes[j]*i]=true;}}
}
void divide(int n)
{for(int i=0;primes[i]<=n/primes[i];i++){int p=primes[i];if(n%p==0){int s=0;while(n%p==0) n/=p,s++;f[p]=max(f[p],s);}}if(n>1)f[n]=max(f[n],1);
}
int main()
{int l,r;cin>>l>>r;init(r);for(int j=l;j<=r;j++)if(st[j])divide(j);long long res=1;for(int i=0;i<cnt;i++)if(f[primes[i]]){while(f[primes[i]]--)res=res*primes[i]%mod;}if(res==1) cout<<-1;else cout<<res;return 0;
}