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

ydc的博客

 
 
 

日志

 
 

bzoj 2820 YY的GCD  

2013-06-05 22:40:13|  分类: bzoj |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |
YY好厉害,一定是个大神犇


假设f(i)表示gcd(x,y)=i,x<=n,y<=m的对数
ans=Σf(d) d是个质数 
f(i)=Σμ(k)*[n/k]*[m/k](这一步不会做可以去看bzoj 1101,具体做法跟ΣΣgcd(i,j)类似,用到的结论是Σμ(d)=e(n),d|n。而e(i)的定义为e(1)=1;e(i)=0(i≠1))
所以ans=Σμ(k)*[n/d/k]*[m/d/k]
有个结论是说,在向下取整的除法下满足结合律,故n/d/k=n/(d*k)
设x=d*k,则ans=Σμ(x/i)*[n/x]*[m/x] 而i|x且i是质数 
再设F(x)=Σμ(x/i) (i|x&&i是质数),代入原式得ans=ΣF(x)*[n/x]*[m/x] 
设g(x)为x分解质因数后质因子指数和,而h(x)为质因子数 
若g(x)==h(x)   F(x)=(-1)^(h(x)-1)*h(x)
若g(x)==h(x)+1 F(x)=(-1)^h(x)
若g(x)>h(x)+1  F(x)=0 
而g,h虽然不是积性函数,但还是很容易用线性筛法筛出来的。筛出来之后用前缀和维护
于是就变成了经典的O(n)预处理O(sqrt(n))查询的题目

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<cmath>
#include<algorithm>
#define maxn 10000010
using namespace std;
typedef long long LL;
const int sign[]={1,-1};
LL Sum[maxn];
void Prepare(int n)
{
static bool flag[maxn];
static int g[maxn],h[maxn],prime[maxn];
int top=0;
for(int i=2;i<=n;i++)
{
if(flag[i]==false)
{
g[i]=1,h[i]=1;
prime[++top]=i;
}
for(int j=1;j<=top&&prime[j]<=n/i;j++)
{
flag[i*prime[j]]=true;
if(i%prime[j]==0)
{
g[i*prime[j]]=g[i]+1;
h[i*prime[j]]=h[i];
break;
}
else
{
g[i*prime[j]]=g[i]+1;
h[i*prime[j]]=h[i]+1;
}
}
}
for(int i=2;i<=n;i++)
{
int fx;
if(g[i]==h[i])
fx=sign[(h[i]-1)&1]*h[i];
else if(g[i]==h[i]+1)
fx=sign[h[i]&1];
else
fx=0;
Sum[i]=Sum[i-1]+fx;
}
}
LL solve(LL n,LL m)
{
if(n>m)
swap(n,m);
LL ans=0;
for(int i=1,nexti;i<=n;i=nexti+1)
{
int ta=n/i,tb=m/i;
nexti=min(n/ta,m/tb);
ans=ans+(Sum[nexti]-Sum[i-1])*ta*tb;
}
return ans;
}
int main()
{
Prepare(10000000);
int test,a,b;
for(scanf("%d",&test);test;test--)
{
scanf("%d %d",&a,&b);
printf("%lld\n",solve(a,b));
}
return 0;
}



  评论这张
 
阅读(953)| 评论(2)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

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

页脚

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