2820: YY的GCD
Time Limit: 10 Sec Memory Limit: 512 MB
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
/*
莫比乌斯.
最后用除法分块..
筛莫比乌斯函数部分:
显然每个素数直接计算mu[i]=-1.
我们知道莫比乌斯函数值是(-1)^k,k是互异质数的个数.
对于一个合数x,令它质因子的最小的那个为p1,
则有x=p1*t1,另设一个与异于p1的质因子为p2.
则有p1*t1=p2*t2.
因为p1与p2互素,所以p2|t1,p1|t2.
所以当i枚举到t2时,因为p1|t2,所以退出
**有一个疑问:就是如果有一个数x1>x,那直接退出以后是不是会影响x1函数值的计算???数学不好没证出来orz**
假如有一个x1=t1*p,且p是x1最大的质因数.
当i枚举到t1时,计算一下x的函数值.
所以我们保证算的每一个合数的莫比乌斯函数的时候
都是在最后一个计算素数的时候的
即每个函数值都只计算了一次.
复杂度是O(n)哒.
*/
#include<iostream>
#include<cstdio>
#define MAXN 10000001
#define LL long long
using namespace std;
int mu[MAXN],pri[MAXN],tot,g[MAXN],sum[MAXN],last;
LL ans,n,m;
bool vis[MAXN];
void pre()
{
mu[1]=1;
for(int i=2;i<=MAXN-1;i++)
{
if(!vis[i]) pri[++tot]=i,mu[i]=-1,g[i]=1;
for(int j=1;j<=tot&&i*pri[j]<=MAXN-1;j++)
{
vis[i*pri[j]]=true;
if(i%pri[j]) mu[i*pri[j]]=-mu[i],g[i*pri[j]]=mu[i]-g[i];
else {
mu[i*pri[j]]=0;g[i*pri[j]]=mu[i];break;
}
}
}
for(int i=1;i<=MAXN-1;i++) sum[i]=sum[i-1]+g[i];
}
int main()
{
int t,x,y;pre();
scanf("%d",&t);
while(t--)
{
scanf("%lld%lld",&n,&m);
if(n>m) swap(n,m);
ans=0;
for(LL i=1;i<=n;i=last+1)
{
last=min(n/(n/i),m/(m/i));
ans+=(n/i)*(m/i)*(sum[last]-sum[i-1]);
}
printf("%lld\n",ans);
}
return 0;
}
Bzoj 2820: YY的GCD(莫比乌斯反演+除法分块)的更多相关文章
-
[BZOJ 2820] YY的gcd(莫比乌斯反演+数论分块)
[BZOJ 2820] YY的gcd(莫比乌斯反演+数论分块) 题面 给定N, M,求\(1\leq x\leq N, 1\leq y\leq M\)且gcd(x, y)为质数的(x, y)有多少对. ...
-
BZOJ 2820: YY的GCD [莫比乌斯反演]【学习笔记】
2820: YY的GCD Time Limit: 10 Sec Memory Limit: 512 MBSubmit: 1624 Solved: 853[Submit][Status][Discu ...
-
bzoj 2820 YY的GCD 莫比乌斯反演
题目大意: 给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对 这里就抄一下别人的推断过程了 后面这个g(x) 算的方法就是在线性 ...
-
bzoj 2820 YY的GCD - 莫比乌斯反演 - 线性筛
Description 神犇YY虐完数论后给傻×kAc出了一题给定N, M,求1<=x<=N, 1<=y<=M且gcd(x, y)为质数的(x, y)有多少对kAc这种 傻×必 ...
-
BZOJ 2820: YY的GCD 莫比乌斯反演_数学推导_线性筛
Code: #include <cstdio> #include <algorithm> #include <cstring> #include <vecto ...
-
BZOJ 2820 YY的GCD ——莫比乌斯反演
我们可以枚举每一个质数,那么答案就是 $\sum_{p}\sum_{d<=n}\mu(d)*\lfloor n / pd \rfloor *\lfloor m / pd \rfloor$ 直接做 ...
-
Bzoj 2301: [HAOI2011]Problem b(莫比乌斯反演+除法分块)
2301: [HAOI2011]Problem b Time Limit: 50 Sec Memory Limit: 256 MB Description 对于给出的n个询问,每次求有多少个数对(x, ...
-
洛谷 - P2257 - YY的GCD - 莫比乌斯反演 - 整除分块
https://www.luogu.org/problemnew/show/P2257 求 \(n,m\) 中 \(gcd(i,j)==p\) 的数对的个数 求 $\sum\limits_p \sum ...
-
【莫比乌斯反演】关于Mobius反演与gcd的一些关系与问题简化(bzoj 2301 Problem b&;&;bzoj 2820 YY的GCD&;&;BZOJ 3529 数表)
首先我们来看一道题 BZOJ 2301 Problem b Description 对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd( ...
随机推荐
-
数据写入文本文件并读出到浏览器的PHP代码
<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Transitional//EN" "http://www.w3.org/ ...
-
【jQuery UI 1.8 The User Interface Library for jQuery】.学习笔记.8.Datepicker控件
默认datepicker的安装启用 探索它的配置选项 安装启用一个触发按钮 配置一个供选择的动画 dateFormat选项 简单的国际化 多月datepicker 日期范围选择 datepicker的 ...
-
ORACLE DATAGURARD 折腾记二
前文再续,书接上一回,这次折腾Data Guard的一个重要目的是利用switchover实现机器的升级,怎么switchover呢?按照我的理解,Data Guard的角色切换是这样一个过程: (1 ...
-
-_-#【Canvas】
context.lineWidth = 0.5 incorrect display lineWidth=1 at html5 canvas canvas.save() canvas.restore() ...
-
数据结构-二叉树 C和C++实现
二叉树,指针域具有两个下一节点的特殊链表结构. 先来看看它的结构 (此处补图) 来看程序中需要使用到的概念: 树根:二叉树的第一个节点 子树:对于某一个节点指针域指向的节点,左指针指向的节点为左子节点 ...
-
UITableViewBase&;nbsp;UI_09
1.UITableView API文档总结: 1.UITableView的父类时,UIScrollView,所以它是可以滚动的,但是只能在竖直方向滚动. 2.UITableView是iOS中 ...
-
(一)STL体系结构基础介绍
一.STL六大部件 容器(Containers):存放元素,内存由分配器搞定 分配器(Allocator):支持容器的内存分配 算法:操作容器元素的函数.与OO不同(面向对象将元素与函数放到一个类里) ...
-
Python 执行主程序
主程序里的代码包含的东西比较多, 如果在程序的.py文件里执行还要再调一遍方法, 但通常这个调用在测试完结后是要删掉的. 那么问题来了, 如果把这个代码直接发给别人, 执行时要再加上调用, 这个就很烦 ...
-
[na]数据包由于isp不稳定丢包-seq&;ack
知识参考: http://www.xianren.org/net/wireshark-q.html 背景 总行wac管理分行ap.手机终端打不开portal页面. 2,分别抓包(portal页面从wa ...
-
Unity容器声明周期管理
Having said that, here is a solution that you can use with the Unity container: Create some custom a ...