GoldenPotato137的小屋
  • 留言板
  • PCB信仰尺
  • IP签名图
GoldenPotato的ACM小屋
一名HITer/LLer/ACMer的ACM(前OI)博客
  1. 首页
  2. 数学
  3. 反演
  4. 正文

[Luogu P3455] [POI2007]ZAP-Queries

2019年03月04日 283点热度 0人点赞 0条评论

题面

传送门:洛咕


Solution

这题比这题不懂简单到哪里去了

好吧,我们来颓柿子。
为了防止重名,以下所有柿子中的$x$既是题目中的$d$
为了方便讨论,以下柿子均假设$b>=a$
为了方便书写,以下除号均为向下取整
题目要求的显然是:
$\large \sum_{i=1}^{a}\sum_{j=1}^{b}[gcd(i,j)=x]$

根据套路,我们这里要先把这个$x$除掉
$\large \sum_{i=1}^{a/x}\sum_{j=1}^{b/x}[gcd(i,j)=1]$

再根据套路,根据莫比乌斯函数中$[x=1]=\sum_{d|x}\mu(d)$的性质,我们把这个$gcd(i,j)$略作转换:
$\large \sum_{i=1}^{a/x}\sum_{j=1}^{b/x}\sum_{d|gcd(i,j)}\mu(d)$

再次根据套路,我们把$d$的和号改成枚举$d$的形式:
$\large \sum_{i=1}^{a/x}\sum_{j=1}^{b/x}\sum_{d=1}^{a/x}\mu(d)*[d|gcd(i,j)]$
显然,我们可以把$\mu(d)$和它前面的和号提到前面去
$\large \sum_{d=1}^{a/x}\mu(d)\sum_{i=1}^{a/x}\sum_{j=1}^{b/x}[d|gcd(i,j)]$
显然,若要$[d|gcd(i,j)]=1$,则$i,j$都必须为$d$的倍数
$\large \sum_{d=1}^{a/x}\mu(d)\frac{a}{x*d}\frac{b}{x*d}$

OK,到此为止,我们所有东西都可以算了。
前面那个$\mu(d)$可以配上后面的两个和号用整除分块的方法前缀和计算即可。如果不是很清楚的话可以看一下代码。
时间复杂度$O(m*\sqrt n)$

完结撒花✿✿ヽ(°▽°)ノ✿0


Code

//Luogu P3455 [POI2007]ZAP-Queries
//Jan,22ed,2019
//莫比乌斯反演
#include<iostream>
#include<cstdio>
using namespace std;
long long read()
{
    long long x=0,f=1; char c=getchar();
    while(!isdigit(c)){if(c=='-') f=-1;c=getchar();}
    while(isdigit(c)){x=x\*10+c-'0';c=getchar();}
    return x\*f;
}
const int N=50000+100;
const int M=50000;
int cnt_p,prime[N],mu[N];
bool noPrime[N];
void GetPrime(int n)
{
    noPrime[1]=true,mu[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(noPrime[i]==false)
            prime[++cnt_p]=i,mu[i]=-1;
        for(int j=1;j<=cnt_p and i\*prime[j]<=n;j++)
        {
            noPrime[i\*prime[j]]=true;
            if(i%prime[j]==0)
            {
                mu[i\*prime[j]]=0;
                break;
            }
            mu[i\*prime[j]]=mu[i]\*mu[prime[j]];
        }
    }
}
long long pre_mu[N];
int main()
{
    GetPrime(M);
    for(int i=1;i<=M;i++)
        pre_mu[i]=pre_mu[i-1]+mu[i];

    int T=read();
    for(;T>0;T--)
    {
        long long a=read(),b=read(),x=read();

        long long ans=0;
        if(a>b) swap(a,b);
        a/=x,b/=x;
        for(int l=1,r;l<=a;l=r+1)
        {
            r=min(a/(a/l),b/(b/l));
            ans+=(pre_mu[r]-pre_mu[l-1])\*(a/l)\*(b/l);
        }

        printf("%lld\n",ans);
    }
    return 0;
}

本作品采用 知识共享署名 4.0 国际许可协议 进行许可
标签: 数学
最后更新:2019年03月04日

GoldenPotato

HITer/ACMer/永远的OIer/数院/LLer/睿智的群星玩家+1000

点赞
< 上一篇
下一篇 >

文章评论

取消回复

GoldenPotato

HITer/ACMer/永远的OIer/数院/LLer/睿智的群星玩家+1000

NNEZ的Friends呢
  • %%%hzq dalao
  • 单向%%%神仙Maxwei_wzj
  • 可爱(?)的ComputerEngine 学弟
  • 安心退役的(?)wpy dalao
  • 把我按在地上锤的lizbaka julao
外校的Friends呢
  • %%% OItby
  • %%%神仙 冒泡ioa
  • %%%神仙attack204
  • allenyou
  • ChenHacker's Blog
  • Chhokmah姐姐() 的博客
  • CpZhao
  • stO神仙 gzy Orz
  • Woshiluo's Notebook
  • 可爱的suqingnian dalao
文章归档
  • 37
  • 28
  • 79,086
  • 22,908

COPYRIGHT © 2020 GoldenPotato137的小屋. ALL RIGHTS RESERVED.

THEME KRATOS MADE BY VTROIS

桂ICP备20002051号