注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

ydc的博客

 
 
 

日志

 
 

bzoj 2154 crash的数字表格  

2013-06-06 17:13:19|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
由于不会用各种神奇的软件,所以这道题的题解我写的各种蛋疼
用了我一节自习课……
e(i)=(i==1?1:0)
[a]=a向下取整
n   m                  n   m                                        [n/d] [m/d]
Σ   Σ  lcm(i,j)=Σ Σ   Σ   ab/d(gcd(a,b)==d)=Σ d Σ     Σ     e(gcd(i,j))*i*j
i=1 j=1            d a=1 b=1                                   i=1   j=1

                n   m                         n   m                                     [n/d] [m/d]                         [n/d] [m/d]
设f(n,m)=Σ   Σ   e(gcd(i,j))*i*j=Σ   Σ   Σ         i*j*μ(d)=Σ μ(d) Σ     Σ     i*j*d=Σμ(d)*d^2*Σ     Σ    i*j
               i=1 j=1                      i=1 j=1 d|gcd(i,j)          d         i=1   j=1                            i=1   j=1
        =n    m       n
         Σ    Σ  i*j= Σ  m*(m+1)/2=n*m*(n+1)*(m+1)/4
         i=1 j=1      i=1
将f(n,m)代入原式,可以得到他等于g(n)*一些[n/i]之类的东西,其中g(n)=nΣk*μ(k),可证明g是积性函数
所以g很容易用线性筛法在O(n)时间得到;于是转化成经典问题

 

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#include<ctime>
#define maxn 10000010
#define mod 20101009
#define anti4 15075757
using namespace std;
typedef long long LL;
LL Sum[maxn];
void Prepare(int n)
{
static LL prime[maxn],p[maxn];
int top=0;
Sum[1]=1;
for(int i=2;i<=n;i++)
{
if(p[i]==0)
{
p[i]=1;
prime[++top]=i;
Sum[i]=mod+(LL)i*(i-1)*(-1)%mod;
}
for(int j=1;j<=top&&prime[j]<=n/i;j++)
{
if(i%prime[j]==0)
{
p[i*prime[j]]=p[i];
if(p[i]!=1)
Sum[i*prime[j]]=Sum[p[i]]*Sum[i/p[i]*prime[j]]%mod;
else
Sum[i*prime[j]]=mod+(LL)i*prime[j]*(prime[j]-1)*(-1)%mod;
break;
}
else
{
Sum[i*prime[j]]=Sum[i]*Sum[prime[j]]%mod;
p[i*prime[j]]=i;
}
}
}
for(int i=2;i<=n;i++)
Sum[i]=(Sum[i-1]+Sum[i])%mod;
}
LL work(LL n,LL m)
{
if(n>m)
swap(n,m);
LL ans=0;
for(LL i=1,nexti;i<=n;i=nexti+1)
{
LL ta=n/i,tb=m/i;
nexti=min(n/ta,m/tb);
ans=(ans+(Sum[nexti]-Sum[i-1]+mod)%mod*ta%mod*tb%mod*(ta+1)%mod*(tb+1)%mod)%mod;
}
return ans*anti4%mod;
}
int main()
{
LL n,m;
scanf("%lld %lld",&n,&m);
Prepare(max(n,m));
printf("%lld\n",work(n,m));
return 0;
}



  评论这张
 
阅读(944)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017