Description

去年的Lucas非常喜歡數論題，但是一年以后的Lucas卻不那么喜歡了。

在整理以前的試題時，發現了這樣一道題目“求Sigma(f(i)),其中1<=i<=N”，其中 表示i的約數個數。他現在長大了，題目也變難了。

求如下表達式的值：

其中 表示ij的約數個數。

他發現答案有點大，只需要輸出模1000000007的值。

Input

第一行一個整數n。

Output

一行一個整數ans，表示答案模1000000007的值。

Sample Input

2

Sample Output

8

HINT

對于100%的數據n <= 10^9。

Solution

弱化版在【刷題】BZOJ 3994 [SDOI2015]約數個數和

式子一模一樣

把最后的式子用杜教篩求就好了

#include<bits/stdc++.h> #define ui unsigned int #define ll long long #define db double #define ld long double #define ull unsigned long long const int MAXN=1000000+10,Mod=1e9+7; int n,cnt,vis[MAXN],prime[MAXN],mu[MAXN],s[MAXN]; std::map<int,ll> M; template<typename T> inline void read(T &x) {T data=0,w=1;char ch=0;while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();if(ch=='-')w=-1,ch=getchar();while(ch>='0'&&ch<='9')data=((T)data<<3)+((T)data<<1)+(ch^'0'),ch=getchar();x=data*w; } template<typename T> inline void write(T x,char ch='\0') {if(x<0)putchar('-'),x=-x;if(x>9)write(x/10);putchar(x%10+'0');if(ch!='\0')putchar(ch); } template<typename T> inline void chkmin(T &x,T y){x=(y<x?y:x);} template<typename T> inline void chkmax(T &x,T y){x=(y>x?y:x);} template<typename T> inline T min(T x,T y){return x<y?x:y;} template<typename T> inline T max(T x,T y){return x>y?x:y;} inline void init() {memset(vis,1,sizeof(vis));vis[0]=vis[1]=0;mu[1]=1;for(register int i=2;i<MAXN;++i){if(vis[i]){prime[++cnt]=i;mu[i]=-1;}for(register int j=1;j<=cnt&&i*prime[j]<MAXN;++j){vis[i*prime[j]]=0;if(i%prime[j])mu[i*prime[j]]=-mu[i];else break;}}for(register int i=1;i<MAXN;++i)s[i]=(s[i-1]+mu[i])%Mod; } inline ll S(int x) {if(x<MAXN)return s[x];if(M.find(x)!=M.end())return M[x];ll res=0;for(register int i=2;;){if(i>x)break;int j=x/(x/i);(res+=1ll*(j-i+1)*S(x/i)%Mod)%=Mod;i=j+1;}return M[x]=(1-res+Mod)%Mod; } inline ll f(int x) {ll res=0;for(register int i=1;;){if(i>x)break;int j=x/(x/i);(res+=1ll*(j-i+1)*(x/i)%Mod)%=Mod;i=j+1;}return res; } int main() {read(n);init();ll res=0;for(register int i=1;;){if(i>n)break;int j=n/(n/i);ll now=f(n/i);(res+=1ll*(S(j)-S(i-1)+Mod)%Mod*now%Mod*now%Mod)%=Mod;i=j+1;}write(res,'\n');return 0; }

轉載于:https://www.cnblogs.com/hongyj/p/9562625.html

總結

以上是生活随笔為你收集整理的【刷题】BZOJ 4176 Lucas的数论的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。