怎么制作公司自己网站,php小型网站源码,西安网站开发的未来发展,小区物业管理系统Description 去年的Lucas非常喜欢数论题#xff0c;但是一年以后的Lucas却不那么喜欢了。 在整理以前的试题时#xff0c;发现了这样一道题目“求Sigma(f(i)),其中1iN”#xff0c;其中 表示i的约数个数。他现在长大了#xff0c;题目也变难了。 求如下表达式的值但是一年以后的Lucas却不那么喜欢了。 在整理以前的试题时发现了这样一道题目“求Sigma(f(i)),其中1iN”其中 表示i的约数个数。他现在长大了题目也变难了。 求如下表达式的值 其中 表示ij的约数个数。 他发现答案有点大只需要输出模1000000007的值。 Input 第一行一个整数n。 Output 一行一个整数ans表示答案模1000000007的值。 Sample Input 2 Sample Output 8 HINT 对于100%的数据n 10^9。 Solution 弱化版在【刷题】BZOJ 3994 [SDOI2015]约数个数和 式子一模一样 把最后的式子用杜教筛求就好了 #includebits/stdc.h
#define ui unsigned int
#define ll long long
#define db double
#define ld long double
#define ull unsigned long long
const int MAXN100000010,Mod1e97;
int n,cnt,vis[MAXN],prime[MAXN],mu[MAXN],s[MAXN];
std::mapint,ll M;
templatetypename T inline void read(T x)
{T data0,w1;char ch0;while(ch!-(ch0||ch9))chgetchar();if(ch-)w-1,chgetchar();while(ch0ch9)data((T)data3)((T)data1)(ch^0),chgetchar();xdata*w;
}
templatetypename T inline void write(T x,char ch\0)
{if(x0)putchar(-),x-x;if(x9)write(x/10);putchar(x%100);if(ch!\0)putchar(ch);
}
templatetypename T inline void chkmin(T x,T y){x(yx?y:x);}
templatetypename T inline void chkmax(T x,T y){x(yx?y:x);}
templatetypename T inline T min(T x,T y){return xy?x:y;}
templatetypename T inline T max(T x,T y){return xy?x:y;}
inline void init()
{memset(vis,1,sizeof(vis));vis[0]vis[1]0;mu[1]1;for(register int i2;iMAXN;i){if(vis[i]){prime[cnt]i;mu[i]-1;}for(register int j1;jcnti*prime[j]MAXN;j){vis[i*prime[j]]0;if(i%prime[j])mu[i*prime[j]]-mu[i];else break;}}for(register int i1;iMAXN;i)s[i](s[i-1]mu[i])%Mod;
}
inline ll S(int x)
{if(xMAXN)return s[x];if(M.find(x)!M.end())return M[x];ll res0;for(register int i2;;){if(ix)break;int jx/(x/i);(res1ll*(j-i1)*S(x/i)%Mod)%Mod;ij1;}return M[x](1-resMod)%Mod;
}
inline ll f(int x)
{ll res0;for(register int i1;;){if(ix)break;int jx/(x/i);(res1ll*(j-i1)*(x/i)%Mod)%Mod;ij1;}return res;
}
int main()
{read(n);init();ll res0;for(register int i1;;){if(in)break;int jn/(n/i);ll nowf(n/i);(res1ll*(S(j)-S(i-1)Mod)%Mod*now%Mod*now%Mod)%Mod;ij1;}write(res,\n);return 0;
} 转载于:https://www.cnblogs.com/hongyj/p/9562625.html
