解题思路
1.只有有两个及以上不同质因子的数才会有贡献
2.对于最小公倍数,若将每个数质因数分解,最小公倍数即为每一个质因子的最高幂次相乘,可用线性筛筛取素数
3.如何确定每一个质因子的最高幂次,因为该数要有两个及以上不同质因子,可将其乘以除他之外最小的素数确定,如:确定2的最高幂次可乘以3,最高幂次为对n/3取对数;确定5的最高幂次可乘以2,最高幂次为对n/2取对数
4.最后一点,用线性筛筛素数时,不必筛到n,因为如果一个素数大于n/2,那么由他组成的有两个及以上不同质因子的数必定大于n,即线性筛筛到n/2即可
AC代码
#include <bits/stdc++.h> #define io ios::sync_with_stdio(false); cin.tie(0); cout.tie(0) #define maxn 160000010 using namespace std; typedef long long ll; const int inf=0x3f3f3f3f; const int MOD=1000000007; const double pi=acos(-1.0); inline int lowbit(int x){ return x&(-x);} int v[maxn]; int prime[maxn]; int cnt; ll qpow(ll a,int b){ ll ans=1; while(b!=0){ if(b&1==1) ans=ans*a%MOD; a=a*a%MOD; b>>=1; } return ans; } int main() { io; int n; cin>>n; if(n<=5) cout<<"empty\n"; //n小于等于5时,不存在有贡献的数,特判一下 else{ for(int i=2;i<=n/2;i++){ if(v[i]==0){ v[i]=i; prime[++cnt]=i;} for(int j=1;j<=cnt;j++){ if(prime[j]>v[i]||i*prime[j]>n/2) break; v[i*prime[j]]=prime[j]; } } ll ans=1; ans=ans*qpow(2,(int)(log(n/3)/log(2)))%MOD; //对数运算时,用换底公式 for(int i=2;i<=cnt;i++){ ans=ans*qpow(prime[i],(int)(log(n/2)/log(prime[i])))%MOD; } cout<<ans<<endl; } return 0; }