【bzoj2820】【YY的gcd】【莫比乌斯反演】

2024-02-20 15:38

本文主要是介绍【bzoj2820】【YY的gcd】【莫比乌斯反演】,希望对大家解决编程问题提供一定的参考价值,需要的开发者们随着小编来一起学习吧!

Description
神犇YY虐完数论后给傻×kAc出了一题
给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对
kAc这种傻×必然不会了,于是向你来请教……
多组输入
Input
第一行一个整数T 表述数据组数
接下来T行,每行两个正整数,表示N, M
Output
T行,每行一个整数表示第i组数据的结果
Sample Input
2
10 10
100 100
Sample Output
30
2791
HINT
T = 10000
N, M <= 10000000
题解:
设p为质数,暴力搞的话显然是

pd=1npnpdmpdu(d)

设T=pd,稍微化一下可以变成
T=1nnTmTp|Tu(Tp)

设g[t]= p|Tu(Tp)
考虑只要求出g数组就可以 n 处理询问了。
g数组可以枚举每个质数然后更新它的倍数.
可以证明这样处理是O(n)的。

#include<iostream>
#include<cstdio>
#include<cstring>
#define N 10000010
using namespace std;
int u[N],p[N],n,m,t,pos;
long long g[N],ans;
bool f[N];
void pre(){u[1]=1;for (int i=2;i<=N-10;i++){if (!f[i]){p[++p[0]]=i;u[i]=-1;}for (int j=1;j<=p[0]&&i*p[j]<=N-10;j++){f[i*p[j]]=1;if (i%p[j]==0){u[i*p[j]]=0;break;}u[i*p[j]]=-u[i];}}for (int i=1;i<=p[0];i++)for (int j=1;j<=(N-10)/p[i];j++)g[p[i]*j]+=(long long)u[j];for (int i=1;i<=N-10;i++) g[i]+=g[i-1];
}
int main(){ scanf("%d",&t);pre();while (t--){scanf("%d%d",&n,&m);ans=0;if (n>m) swap(n,m);for (int i=1;i<=n;i=pos+1){pos=min(n/(n/i),m/(m/i));ans+=(long long)(n/i)*(long long)(m/i)*(g[pos]-g[i-1]); }printf("%lld\n",ans);}
}

这篇关于【bzoj2820】【YY的gcd】【莫比乌斯反演】的文章就介绍到这儿,希望我们推荐的文章对编程师们有所帮助!



http://www.chinasem.cn/article/728692

相关文章

hdu6053 TrickGCD 莫比乌斯反演

TrickGCD Time Limit: 5000/2500 MS (Java/Others)    Memory Limit: 262144/262144 K (Java/Others) Problem Description You are given an array  A  , and Zhu wants to know there are how many d

每日一题~cf 970 div3 (A思维,B小模拟,C二分,D排列数建图成环,E 26个字母暴力+前缀和,F 逆元,G 数论gcd )

A 题意: 有 a 个1 ,b 个2.问是否能将这些数划分为两个数值相等的集合。 输出 YES 或者 NO —————— 问题等价于 将数组 分成两个数值相同的数组。所以sum 应该是偶数。也就是说 1 的个数是偶数。在i1的个数是偶数的情况下,将 2 分成两份,如果2 的个数是偶数,OK。如果是奇数那么需要1来补齐,如果1 的个数大于等于2那么可以补齐。(1 的个数是偶数,需要2个1来补齐,剩下

iOS——GCD再学习

GCD 使用GCD好处,具体如下: GCD 可用于多核的并行运算;GCD 会自动利用更多的 CPU 内核(比如双核、四核);GCD 会自动管理线程的生命周期(创建线程、调度任务、销毁线程);程序员只需要告诉 GCD 想要执行什么任务,不需要编写任何线程管理代码。 任务与队列 概念 **任务:就是执行操作的意思,换句话说就是你在线程中执行的那段代码。**在 GCD 中是放在 block 中

GCD常用函数拾遗

目录 dispatch_block_t监听block执行结束dispatch_block_waitdispatch_block_notify 撤销block总结参考 这几天偶尔又回顾了下GCD的知识。之前我一直以为自己对于GCD已经大体有个整体掌握了,却发现仍还有一些知识点的遗漏。于是写在这里,算是对之前GCD常用函数文章的补充。 dispatch_block_t 在GCD中

环上k划分的和的gcd的最大值【gcd基本性质的利用】

今早看到的题,想了下会做了,但是觉得这题挺有意思的,于是打算写一下做法。本题利用了gcd的基本性质:更相减损法以及结合律,平时做gcd的题基本没用到过这两性质,而本题对这性质进行了充分利用。 思路: 首先我们考虑给一个序列,我们该怎么做。 令 fn=∑ni=1ai f_n=\sum_{i=1}^n a_i。 我们考虑序列的一个 k+1 k+1划分 fx1,fx2−fx1,fx3−fx2

猫猫学iOS(五十一)多线程网络之GCD下载合并图片_队列组的使用

猫猫分享,必须精品 原创文章,欢迎转载。转载请注明:翟乃玉的博客 地址:http://blog.csdn.net/u013357243?viewmode=contents 合并图片(图片水印)第一种方法 效果 实现: 思路: 1.分别下载2张图片:大图片、LOGO 2.合并2张图片 3.显示到一个imageView身上 // 异步下载dispatch_async(dis

猫猫学iOS(五十)多线程网络之GCD简单介绍(任务,队列)

猫猫分享,必须精品 原创文章,欢迎转载。转载请注明:翟乃玉的博客 地址:http://blog.csdn.net/u013357243?viewmode=contents GCD简单介绍 1.什么是GCD? 全称是Grand Central Dispatch,可译为“牛逼的中枢调度器” 纯C语言,提供了非常多强大的函数 2.GCD的优势 GCD是苹果公司为多核的并行运算提出的解决方

iOS面试:GCD的队列(dispatch_queue_t)分哪两种类型?

在 iOS 开发中,Grand Central Dispatch (GCD) 提供了强大的并发执行任务的能力。dispatch_queue_t 是 GCD 中的一个重要对象,用于管理和调度要执行的任务。GCD 的队列主要可以分为两种类型: 1. 串行队列(Serial Queues) 串行队列确保在同一时间只执行一个任务。任务按照它们被添加的顺序逐个执行。这种队列适用于需要操作共享资源的场景,

学习笔记 ---- 莫比乌斯反演总结

文章目录 概述前置知识数论分块狄利克雷卷积积性函数 莫比乌斯函数定义性质 莫比乌斯反演因子形式倍数形式 例题周期性字符串互质数对[NOI2010D1T1]能量采集BZOJ2820 YY的GCD[SDOI2015] 约数个数和BZOJ4407 于神之怒加强版【BZOJ2693】jzptab最小公倍数之和[bzoj3529-Sdoi2014] 数表 练习题51nod 1675 序列变换BZOJ3

GCD部分用法

1,用gcd延迟执行任务 如果我们需要某个方法在一段时间后执行,那么我们常常会调用这样的方法 - (void)viewDidLoad{     [super viewDidLoad];     [self performSelector:@selector(printString:) withObject:@"Grand Central Dispatch" afterDel