bzoj 2721

 题解：首先推一发式子：

原式：

通分，移项：

打开，合并：

再移项，得：

设：

那么：

代入：

化简：

因为x是整数，所以x的数量显然为能使取得整数的t的个数，也就是求的约数个数

而根据约数个数和公式(设一个数)

可以将前n个数质因子分解，然后将质因子的幂次相乘，最后将所有幂次*2+1后乘在一起即可。

#include 
#include 
#include 
#include 
#include 
#include 
#include 
#include 
#define ll long long
#define mode 1000000007
#define maxn 1000000
using namespace std;
ll fac[1000005];
ll pri[1000005];
bool used[1000005];
int tot=0;
int n;
void init()
{scanf("%d",&n);for(int i=2;(ll)i*i<=n;i++){if(!used[i]){pri[++tot]=i;}for(int j=1;j<=tot&&(ll)i*pri[j]<=n;j++){used[i*pri[j]]=1;if(i%pri[j]==0){break;}}}for(int i=2;i<=n;i++){int t=i;for(int j=1;(ll)pri[j]*pri[j]<=t&&j<=tot;j++){while(t%pri[j]==0){fac[pri[j]]++;t/=pri[j];	if(fac[pri[j]]>=mode){fac[pri[j]]-=mode;}}}if(t!=1){fac[t]++;if(fac[t]>=mode){fac[t]-=mode;}		}}  ll ans=1;for(int i=1;i<=n;i++){fac[i]<<=1;fac[i]%=mode;ans*=(fac[i]+1);ans%=mode;}printf("%lld\n",ans);
}
int main()
{init();return 0;
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！