BZOJ 2301: [HAOI2011]Problem b 莫比乌斯反演

时间:2022-09-23 00:13:45

2301: [HAOI2011]Problem b

Time Limit: 50 Sec  Memory Limit: 256 MB
Submit: 1007  Solved: 415
[Submit][Status]

Description

对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数。

Input

第一行一个整数n,接下来n行每行五个整数,分别表示a、b、c、d、k

Output

共n行,每行一个整数表示满足要求的数对(x,y)的个数

Sample Input

2

2 5 1 5 1

1 5 1 5 2

Sample Output

14

3

HINT

100%的数据满足:1≤n≤50000,1≤a≤b≤50000,1≤c≤d≤50000,1≤k≤50000

 
mobius反演,与“能量采集”不同的是,这道题如果不加一点优化的话,是一定会TLE的。然后考虑优化:
  ans+=segma(mu[i]*(a/i)*(b/i))
由于对于一个给定的区间[l,r], a/l=a/r   b/l=b/r,可以对对这个区间统一处理。
  ans+=segma((sum[r]-sum[l-1])*(a/l)*(n/l))
所以令l=i,这里要记一下
  a/(a/i)==r+1
所以剩下的就可以随便搞一下了。
 
 
#include<iostream>
#include<algorithm>
#include<cstring>
#include<cstdio>
using namespace std;
#ifdef unix
#define LL "%lld"
#else
#define LL "%I64d"
#endif
typedef long long qword;
#define MAXN 100000
int prime[MAXN/];
bool pflag[MAXN];
int topp=-;
int mu[MAXN];
int sum[MAXN];
void init()
{
int i,j;
mu[]=;
for (i=;i<MAXN;i++)
{
if (!pflag[i])
{
prime[++topp]=i;
mu[i]=-;
}
for (j=;j<=topp&&prime[j]*i<MAXN;j++)
{
pflag[i*prime[j]]=true;
mu[i*prime[j]]=-mu[i];
if (i%prime[j]==)
{
mu[i*prime[j]]=;
}
}
}
}
qword solve(int a,int b)
{
int l=min(a,b);
int i,j;
int ls,lt;
qword ret=;
for (i=,ls=;i<=l;i=ls+)
{
ls=min((a/(a/i)),(b/(b/i)));
ret+=(qword) (sum[ls]-sum[i-])*(a/i)*(b/i);
}
return ret;
}
int main()
{
int nn;
freopen("input.txt","r",stdin);
init();
scanf("%d",&nn);
int a,b,c,d,n;
qword ans;
int i,j;
for (i=;i<MAXN;i++)sum[i]=sum[i-]+mu[i];
/* for (i=1;i<10;i++)
{
for (j=0;j<10;j++)
{
cout<<i<<" "<<j<<" "<<solve(i,j)<<endl;
}
}
*/
// cout<<solve(2,3);
// return 0;
while (nn--)
{
scanf("%d%d%d%d%d",&a,&b,&c,&d,&n);
ans=solve((a-)/n,(c-)/n)-solve((a-)/n,d/n)-solve(b/n,(c-)/n)+solve(b/n,d/n);
printf(LL "\n",ans);
}
}

BZOJ 2301: [HAOI2011]Problem b 莫比乌斯反演的更多相关文章

  1. Bzoj 2301&colon; &lbrack;HAOI2011&rsqb;Problem b&lpar;莫比乌斯反演&plus;除法分块&rpar;

    2301: [HAOI2011]Problem b Time Limit: 50 Sec Memory Limit: 256 MB Description 对于给出的n个询问,每次求有多少个数对(x, ...

  2. BZOJ&period;2301&period;&lbrack;HAOI2011&rsqb;Problem B&lpar;莫比乌斯反演 容斥&rpar;

    [Update] 我好像现在都看不懂我当时在写什么了=-= \(Description\) 求\(\sum_{i=a}^b\sum_{j=c}^d[(i,j)=k]\) \(Solution\) 首先 ...

  3. BZOJ 2301 &lbrack;HAOI2011&rsqb;Problem b ——莫比乌斯反演

    分成四块进行计算,这是显而易见的.(雾) 然后考虑计算$\sum_{i=1}^n|sum_{j=1}^m gcd(i,j)=k$ 首先可以把n,m/=k,就变成统计&i<=n,j< ...

  4. bzoj 2301&colon; &lbrack;HAOI2011&rsqb;Problem b mobius反演 RE

    http://www.lydsy.com/JudgeOnline/problem.php?id=2301 设f(i)为在区间[1, n]和区间[1, m]中,gcd(x, y) = i的个数. 设F( ...

  5. BZOJ 2301 &lbrack;HAOI2011&rsqb;Problem b &lpar;分块 &plus; 莫比乌斯反演&rpar;

    2301: [HAOI2011]Problem b Time Limit: 50 Sec  Memory Limit: 256 MBSubmit: 6519  Solved: 3026[Submit] ...

  6. BZOJ 2301&colon; &lbrack;HAOI2011&rsqb;Problem b (莫比乌斯反演)

    2301: [HAOI2011]Problem b Time Limit: 50 Sec  Memory Limit: 256 MBSubmit: 436  Solved: 187[Submit][S ...

  7. BZOJ2301&colon; &lbrack;HAOI2011&rsqb;Problem b&lbrack;莫比乌斯反演 容斥原理&rsqb;【学习笔记】

    2301: [HAOI2011]Problem b Time Limit: 50 Sec  Memory Limit: 256 MBSubmit: 4032  Solved: 1817[Submit] ...

  8. bzoj 2301&colon; &lbrack;HAOI2011&rsqb;Problem b

    2301: [HAOI2011]Problem b Time Limit: 50 Sec Memory Limit: 256 MB Submit: 3757 Solved: 1671 [Submit] ...

  9. BZOJ 2301&colon; &lbrack;HAOI2011&rsqb;Problem b&lpar; 数论 &rpar;

    和POI某道题是一样的...  http://www.cnblogs.com/JSZX11556/p/4686674.html 只需要二维差分一下就行了. 时间复杂度O(MAXN + N^1.5) - ...

随机推荐

  1. cocos2dx Sprite的多种创建方法

    1.通过文件创建 Sprite *bg = Sprite::create("backGround.jpg"); 2.通过图片的某个区域创建 SpriteFrame *frame = ...

  2. RabbitMQ 学习开发笔记

    基本概念 ConnectionFactory.Connection.Channel ConnectionFactory.Connection.Channel,这三个都是RabbitMQ对外提供的API ...

  3. The client and server cannot communicate&comma; because they do not possess a common algorithm

    The client and server cannot communicate, because they do not possess a common algorithm This was re ...

  4. opencv模板匹配有趣的链接

    https://docs.opencv.org/3.0-beta/doc/py_tutorials/py_imgproc/py_template_matching/py_template_matchi ...

  5. Azure DevOps Server&colon; 使用Rest Api获取拉取请求Pull Request中的变更文件清单

    需求: Azure DevOps Server 的拉取请求模块,为开发团队提供了强大而且灵活的代码评审功能.拉取请求中变更文件清单,对质量管理人员,是一个宝贵的材料.质量保障人员可以从代码清单中分析不 ...

  6. win&plus;linux双系统安装笔记

    1.出现win与linux只能引导之一启动,此时启动linux并更改启动文件可以用linux自带的grub2引导启动 2.ubuntu64位安装时需要联网,因为其有bug,镜像文件中缺少gurb2,需 ...

  7. 使用pip install XX 命令时报错

    在使用pip命令安装的时候,我遇到这样的报错: C:\Users\86962>pip install Appium-Python-Client Collecting Appium-Python- ...

  8. 使用Serilog输出到ES&lpar;使用笔记&rpar;

    第一步:安装Serilog 使用NuGet包安装以下组件: Serilog.AspNetCoreSerilog.Settings.ConfigurationSerilog.Sinks.ConsoleS ...

  9. SGU 114&period; Telecasting station 三分or找中位数

    题目链接点这儿 一開始想都没想...直接上了三分...结果...sample的答案不一样...可是过了...然后又看了看. . . 发现这不就是高中或者初中出过的求中位数的题么. . .直接找到这些的 ...

  10. 流量监控iftop安装-CentOS7

    继之前撘的服务器后路由器一直崩溃,今天找到了原因.之前被下的木马并没有被删掉,而是一直在传输数据.占用了所有宽带. 官网(http://www.ex-parrot.com/pdw/iftop/down ...