看这个题解吧:http://blog.csdn.net/wubaizhe/article/details/77338332

代码里顺便把几个常用的线性筛附上了。

Key:1、gcd(i,j)==1利用莫比乌斯函数的性质进行转化。

2、变换求和符号的顺序。

3、发现,该式可以递推

4、线性筛约数个数函数。

#include<cstdio>
#include<algorithm>
using namespace std;
#define MOD 1000000007
#define N 1000000
bool notpri[N+5];
int pri[N+5],n,mu[N+5],sum[N+5];
typedef long long ll;
void shai_mu()//线性筛莫比乌斯函数,并处理出前缀和
{
notpri[1]=1; mu[1]=1;
for(int i=2;i<=N;i++){
if(!notpri[i]){
pri[++pri[0]]=i;
mu[i]=-1;
}
for(int j=1;j<=pri[0] && (ll)i*(ll)pri[j]<=(ll)N;j++){
notpri[i*pri[j]]=1;
mu[i*pri[j]]=-mu[i];
if(i%pri[j]==0){
mu[i*pri[j]]=0;
break;
}
}
}
sum[1]=mu[1];
for(int i=2;i<=N;i++){
sum[i]=sum[i-1]+mu[i];
}
}
int ysgs[N+5],facnum[N+5],d[N+5]/*d(i)是辅助数组,记录每个数的最小质因子的幂次*/;
void shai_facnum()//线性筛每个数的约数个数
{
facnum[1]=1;
for(int i=2;i<=N;++i){
if(!notpri[i]){
facnum[i]=2;
d[i]=1;
}
for(int j=1;j<=pri[0] && (ll)i*(ll)pri[j]<=(ll)N;++j){
if(i%pri[j]==0){
facnum[i*pri[j]]=facnum[i]/(d[i]+1)*(d[i]+2);
d[i*pri[j]]=d[i]+1;
break;
}
facnum[i*pri[j]]=facnum[i]*2;
d[i*pri[j]]=1;
}
}
}
int g[N+5];
int main(){
//freopen("hdu6134.in","r",stdin);
shai_mu();
shai_facnum();
g[1]=1;
for(int i=2;i<=N;++i){
g[i]=(g[i-1]+(facnum[i-1]+1))%MOD;
}
for(int i=2;i<=N;++i){
g[i]=(g[i]+g[i-1])%MOD;
}
while(scanf("%d",&n)!=EOF){
int ans=0;
for(int i=1;i<=n;){
ans=(ans+(int)((((ll)(sum[n/(n/i)]-sum[i-1]+(ll)MOD)%(ll)MOD)*(ll)g[n/i])%(ll)MOD))%MOD;
i=n/(n/i)+1;
}
printf("%d\n",ans);
}
return 0;
}
/*
线性筛欧拉函数
void get_eular()
{
pnum = 0;
for(int i = 2; i < MAX; i++)
{
if(!noprime[i])
{
p[pnum ++] = i;
phi[i] = i - 1;
}
for(int j = 0; j < pnum && i * p[j] < MAX; j++)
{
noprime[i * p[j]] = true;
if(i % p[j] == 0)
{
phi[i * p[j]] = phi[i] * p[j];
break;
}
phi[i * p[j]] = phi[i] * (p[j] - 1);
}
}
}
*/

最新文章

  1. Java中对session的简单操作
  2. BZOJ3142 [Hnoi2013]数列
  3. C#: 集合
  4. Ajax与Json的一些总结
  5. windows 下共享内存使用方法示例
  6. springboot 共享session
  7. Magento 2 创建 Widget
  8. Python 爬虫 当当网图书 scrapy
  9. Asch PK Lisk系列之一:安全性
  10. VMware+CentOS7学习记录
  11. Cocos Creator学习二:查找节点和查找组件
  12. Handler processing failed; nested exception is java.lang.NoSuchMethodError: org.apache.commons.codec.digest.DigestUtils.sha1Hex(Ljava/lang/String;)Ljava/lang/String;
  13. web自动化测试---web页面元素的定位
  14. 【九天教您南方cass 9.1】 03 编码法绘制地形图
  15. Linux 虚拟内存机制
  16. elasticsearch mysql logstash 同步 简单配置【环境centos7 elasticsearch 6.0 mysql 5.7 logstash 6.0】
  17. java的事务类型及定义
  18. sql 通过分数字段倒排获取名次的方法
  19. Windows.Devices API in a C# WinForm Win32 Desktop application in Windows 10
  20. KMP + 求最小循环节 --- HDU 1358 Period

热门文章

  1. C# SuperSocket 消息推送
  2. 使用makecontext实现用户线程【转】
  3. Linux进程的创建函数fork()及其fork内核实现解析
  4. monkey测试===关于monkey测试的介绍
  5. 用__builtin_return_address获得程序运行栈情况【转】
  6. (二十一)Makefile例子
  7. 2017多校第7场 HDU 6129 Just do it 找规律
  8. apache加入chkconfig
  9. RSA加密解密与加签验签
  10. C# 笔记——索引器