【题解】Luogu P2257 YY的GCD

时间:2022-09-23 10:49:21

原题传送门

这题需要运用莫比乌斯反演(懵逼钨丝繁衍)

显然题目的答案就是$$ Ans=\sum_{i=1}N\sum_{j=1}M[gcd(i,j)=prime]$$

我们先设设F(n)表示满足\(gcd(i,j)\%t=0\)的数对个数,f(t)表示满足\(gcd(i,j)=t\)的数对个数

$$f(t)=\sum_{i=1}N\sum_{j=1}M[gcd(i,j)=t]$$

$$F(n)=\sum_{n|t}\lfloor \frac{N}{n} \rfloor \lfloor \frac{M}{n} \rfloor$$

那么根据莫比乌斯反演的第二种形式珂以得到

$$f(n)=\sum_{n|t}\mu(\lfloor \frac{t}{n} \rfloor)F(t)$$

所以答案珂以变形为:

$$Ans=\sum_{p \in prime}\sum_{i=1}N\sum_{j-1}M[gcd(i,j)=p)$$

$$=\sum_{p \in prime}f(p) \qquad \qquad \quad$$

$$=\sum_{p \in prime}\sum_{p|t}\mu(\lfloor \frac{t}{p} \rfloor)F(t)$$

我们不枚举p,我们枚举\(\lfloor \frac{t}{p} \rfloor\)

$$Ans=\sum_{p \in prime}\sum_{d=1}^{Min(\frac{N}{p},\frac{M}{p})}\mu(t)F(tp)$$

$$\qquad \qquad \qquad=\sum_{p \in prime}\sum_{d=1}^{Min(\frac{N}{p},\frac{M}{p})}\mu(t)\sum_{n|t}\lfloor \frac{N}{tp} \rfloor \lfloor \frac{M}{tp} \rfloor$$

我们把tp换成T继续变形

$$Ans=\sum_{T=1}^{Min(N,M)}\lfloor \frac{N}{T} \rfloor \lfloor \frac{M}{T} \rfloor(\sum_{p|T,p \in prime}\mu(\frac{T}{p}))$$

这样就珂以用整除分块求了qaq

#include <bits/stdc++.h>
#define N 10000005
#define ll long long
#define getchar nc
using namespace std;
inline char nc(){
static char buf[100000],*p1=buf,*p2=buf;
return p1==p2&&(p2=(p1=buf)+fread(buf,1,100000,stdin),p1==p2)?EOF:*p1++;
}
inline int read()
{
register int x=0,f=1;register char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9')x=(x<<3)+(x<<1)+ch-'0',ch=getchar();
return x*f;
}
inline void write(register ll x)
{
if(!x)putchar('0');if(x<0)x=-x,putchar('-');
static int sta[30];register int tot=0;
while(x)sta[tot++]=x%10,x/=10;
while(tot)putchar(sta[--tot]+48);
}
inline int Min(register int x,register int y)
{
return x<y?x:y;
}
int v[N],miu[N],prim[N],cnt=0,g[N];
ll sum[N];
int main()
{
miu[1]=1;
for(register int i=2;i<=N;++i)
{
if(!v[i])
{
miu[i]=-1;
prim[++cnt]=i;
}
for(register int j=1;j<=cnt&&prim[j]*i<=N;++j)
{
v[i*prim[j]]=1;
if(i%prim[j]==0)
break;
else
miu[prim[j]*i]=-miu[i];
}
}
for(register int i=1;i<=cnt;++i)
for(register int j=1;j*prim[i]<=N;++j)
g[j*prim[i]]+=miu[j];
for(register int i=1;i<=N;++i)
sum[i]=sum[i-1]+(ll)g[i];
int t=read();
while(t--)
{
int n=read(),m=read();
if(n>m)
n^=m^=n^=m;
ll ans=0;
for(register int l=1,r;l<=n;l=r+1)
{
r=Min(n/(n/l),m/(m/l));
ans+=(ll)(n/l)*(m/l)*(sum[r]-sum[l-1]);
}
write(ans),puts("");
}
return 0;
}

【题解】Luogu P2257 YY的GCD的更多相关文章

  1. &lbrack;Luogu P2257&rsqb; YY的GCD &lpar;莫比乌斯函数&rpar;

    题面 传送门:洛咕 Solution 推到自闭,我好菜啊 显然,这题让我们求: \(\large \sum_{i=1}^{n}\sum_{j=1}^{m}[gcd(i,j)\in prime]\) 根 ...

  2. Luogu P2257 YY的GCD

    莫比乌斯反演第一题.莫比乌斯反演入门 数论题不多BB,直接推导吧. 首先,发现题目所求\(ans=\sum_{i=1}^n\sum_{j=1}^m [\gcd(i,j)=prime]\) 考虑反演,我 ...

  3. Luogu P2257 YY的GCD 莫比乌斯反演

    第一道莫比乌斯反演...$qwq$ 设$f(d)=\sum_{i=1}^n\sum_{j=1}^m[gcd(i,j)==d]$ $F(n)=\sum_{n|d}f(d)=\lfloor \frac{N ...

  4. 题解 P2257 YY的GCD

    P2257 YY的GCD 解题思路 果然数论的题是真心不好搞. 第一个莫比乌斯反演的题,好好推一下式子吧..(借鉴了blog) 我们要求的答案就是\(Ans=\sum\limits_{i=1}^{n} ...

  5. 洛谷 P2257 YY的GCD

    洛谷 P2257 YY的GCD \(solution:\) 这道题完全跟[POI2007]ZAP-Queries (莫比乌斯反演+整除分块) 用的一个套路. 我们可以列出答案就是要我们求: \(ans ...

  6. P2257 YY的GCD

    P2257 YY的GCD 题目描述 神犇YY虐完数论后给傻×kAc出了一题 给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对 k ...

  7. 洛谷 P2257 YY的GCD 题解

    原题链接 庆祝: 数论紫题 \(T4\) 达成! 莫比乌斯 \(T1\) 达成! yy 真是个 神犇 前记 之前我觉得: 推式子,直接欧拉筛,筛出个 \(\phi\),然后乱推 \(\gcd\) 就行 ...

  8. P2257 YY的GCD (莫比乌斯反演)

    [题目链接] https://www.luogu.org/problemnew/show/P2257 // luogu-judger-enable-o2 /* -------------------- ...

  9. 洛谷 - P2257 - YY的GCD - 莫比乌斯反演 - 整除分块

    https://www.luogu.org/problemnew/show/P2257 求 \(n,m\) 中 \(gcd(i,j)==p\) 的数对的个数 求 $\sum\limits_p \sum ...

随机推荐

  1. javascript学习笔记(四):事件处理函数和动态创建html标记。

    1 HTML的事件属性  全局事件属性:HTML 4 增加了使事件在浏览器中触发动作的能力,比如当用户点击元素时启动 JavaScript. a. Window 事件属性,针对 window 对象触发 ...

  2. spark在windows下的安装

      Windows下最简的开发环境搭建这里的spark开发环境, 不是为apache spark开源项目贡献代码, 而是指基于spark的大数据项目开发. Spark提供了2个交互式shell, 一个 ...

  3. tcl调用tuxedo的一个demo

    Tuxedo是Oracle的一个商业中间件,一般用于通信. 如下是一个简单的调用tuxedo的so动态库实现,编译后,tcl脚本可以加载并调用这个so库实现对tuxedo的调用. 1. 代码例子,保存 ...

  4. BootStrap——模态框

    模态框(Modal)是BootStrap中很棒的一个插件.可以去BootStrap菜鸟驿站里面看看. 模态框(Modal)是覆盖在父窗体上的子窗体.通常,目的是显示来自一个单独的源的内容,可以在不离开 ...

  5. selinux策略开发

    所用软件: 1.setools -->seaudit  读取日志以确定所需权限 2.Reference Policy  -->  https://github.com/TresysTech ...

  6. 网页布局之flex

    Flex是Flexible Box的缩写,意为“弹性布局”,用来为盒状模型提供最大的灵活性.设为Flex布局以后,子元素的float.clear和vertical-align属性将失效.使用flex ...

  7. Redis自学笔记&colon;4&period;4进阶-消息通知

    4.4消息通知 4.4.1任务队列 传递任务的队列.与任务队列进行交互的实体有两类,一类是生产者,一类是消费者. 生产者将需要处理的任务放入任务队列中,二消费者不断从任务队列中读入任务 信息并执行. ...

  8. IdentityServer4【QuickStart】之设置和概述

    设置和概述 有两个基本的方式来开启一个新的IdentityServer项目: 从头开始 从asp.net Identity模板开始 如果你从头开始,我们提供了一些基于内存中构建的存储,所以你不必一开始 ...

  9. js 正则常用函数 会正则得永生

    正则表达式作为一种匹配处理字符串的利器在很多语言中都得到了广泛实现和应用,web开发本质上是处理字符串(服务端接受请求处理后拼接字符串作为响应,这在早期的CGI编程中最明显,然后客户端解析字符串进行渲 ...

  10. zedboard--基于zedboard的demo系统的boa服务器搭建(二十一)

    zedboard提供的demo系统很迷你,但是也能移植嵌入式Web服务器的.这里就移植boa服务器. 1.下载Boa服务器源代码(安装好了交叉编译器) http://www.boa.org/,选择最后 ...