【莫比乌斯反演】BZOJ1101 [POI2007]zap

Description

  回答T组询问,有多少组gcd(x,y)=d,x<=a, y<=b。T, a, b<=4e5。

Solution

  显然对于gcd=d的,应该把a/d b/d,然后转为gcd=1计算

  计算用莫比乌斯反演相信大家都会

  关键是有T组询问n^2会T

  于是有这样一个优化可以做到每次sqrt(n)

  

  每一次是ret+=mu[i]*(n/i)*(m/i)

  可是除法向下取整所以会导致很多i的(n/i)*(m/i)一样

  具体来说,向下取整得到的结果一定是约数所以对于(n/i)最多2sqrt(n)种

  那么(n/i)*(m/i)放一起也就4sqrt(n)种

  这个序列一定是不上升的,所以考虑对所有的(n/i)*(m/i)视为一块相同的一起算

  那么肯定要记录下mu[i]的前缀和

  如何快速得到每一块的l和r?

  每一块的r肯定要么n%i==0要么m%i==0

  于是用pos=min(n/(n/i),m/(m/i)) 定位

  当然pos+1就是下一块的l了

Code

 1 #include<cstdio>
 2 #include<algorithm>
 3 #include<cstring>
 4 using namespace std;
 5 const int maxn=5e4+5;
 6
 7 int flag[maxn],prime[maxn],cnt;
 8 int mu[maxn],sum[maxn];
 9
10 int getmu(){
11     mu[1]=1;
12     for(int i=2;i<maxn;i++){
13         if(!flag[i]){
14             prime[++cnt]=i;
15             mu[i]=-1;
16         }
17         for(int j=1;i*prime[j]<maxn&&j<=cnt;j++){
18             flag[i*prime[j]]=1;
19             if(i%prime[j]==0){
20                 mu[i*prime[j]]=0;
21                 break;
22             }
23             mu[i*prime[j]]=-mu[i];
24         }
25     }
26     for(int i=1;i<maxn;i++)
27         sum[i]=sum[i-1]+mu[i];
28 }
29
30 int cal(int n,int m){
31     int ret=0,pos;
32     if(n>m) swap(n,m);
33     for(int i=1;i<=n;i=pos+1){
34         pos=min(n/(n/i),m/(m/i));
35         ret+=(sum[pos]-sum[i-1])*(n/i)*(m/i);
36     }
37     return ret;
38 }
39
40 int main(){
41     int T,a,b,d;
42     scanf("%d",&T);
43     getmu();
44
45     while(T--){
46         scanf("%d%d%d",&a,&b,&d);
47         a/=d,b/=d;
48         printf("%d\n",cal(a,b));
49     }
50     return 0;
51 }
时间: 06-22

【莫比乌斯反演】BZOJ1101 [POI2007]zap的相关文章

Bzoj1101 [POI2007]Zap

Time Limit: 10 Sec  Memory Limit: 162 MBSubmit: 2414  Solved: 995[Submit][Status][Discuss] Description FGD正在破解一段密码,他需要回答很多类似的问题:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a,y<=b,并且gcd(x,y)=d.作为FGD的同学,FGD希望得到你的帮助. Input 第一行包含一个正整数n,表示一共有n组询问.(1<=n<= 50000)接下

bzoj 1101 [POI2007]Zap - 莫比乌斯反演

Description FGD正在破解一段密码,他需要回答很多类似的问题:对于给定的整数a,b和d,有多少正整数对x,y,满足x<=a ,y<=b,并且gcd(x,y)=d.作为FGD的同学,FGD希望得到你的帮助. Input 第一行包含一个正整数n,表示一共有n组询问.(1<=n<= 50000)接下来n行,每行表示一个询问,每行三个 正整数,分别为a,b,d.(1<=d<=a,b<=50000) Output 对于每组询问,输出到输出文件zap.out一个正

bzoj 2820 / SPOJ PGCD 莫比乌斯反演

那啥bzoj2818也是一样的,突然想起来好像拿来当周赛的练习题过,用欧拉函数写掉的. 求$(i,j)=prime$对数 \begin{eqnarray*}\sum_{i=1}^{n}\sum_{j=1}^{m}[(i,j)=p]&=&\sum_{p=2}^{min(n,m)}\sum_{i=1}^{\lfloor\frac{n}{p}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{p}\rfloor}[i⊥j]\newline&=&\sum_{p=

hdu1695(莫比乌斯反演)

题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=1695 题意: 对于 a, b, c, d, k . 有 x 属于 [a, b],  y 属于 [c, d], 求 gcd(x, y) = k 的 x, y 的对数 . 其中 a = b = 1 . 注意: (x, y), (y, x) 算一种情况 . 思路: 莫比乌斯反演 可以参考一下: http://blog.csdn.net/lixuepeng_001/article/details/5057

算法学习——莫比乌斯反演(1)

.. 省选GG了,我果然还是太菜了.. 突然想讲莫比乌斯反演了 那就讲吧! 首先我们看一个等式-- (d|n表示d是n的约束) 然后呢,转换一下 于是,我们就发现! 没错!F的系数是有规律的! 规律is here! 公式: 这个有什么卵用呢? 假如说有一道题 F(n)可以很simple的求出来而求f(n)就比较difficult了,该怎么办呢? 然后就可以用上面的式子了 是莫比乌斯函数,十分有趣 定义如下: 若d=1,则=1 若d=p1*p2*p3...*pk,且pi为互异素数,则=(-1)^k

bzoj 1101: [POI2007]Zap

裸的莫比乌斯反演 1 #include<bits/stdc++.h> 2 #define N 100005 3 #define M 10000005 4 #define LL long long 5 #define inf 0x3f3f3f3f 6 using namespace std; 7 inline int ra() 8 { 9 int x=0,f=1; char ch=getchar(); 10 while (ch<'0' || ch>'9') {if (ch=='-')

bzoj2301 [HAOI2011]Problem b【莫比乌斯反演 分块】

传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2301 很好的一道题.首先把每个询问转化为4个子询问,最后的结果就是这四个子询问的记过加加减减,类似二维前缀和.那么问题转化为在1 <= x <= lmtx, 1 <= y <= lmty时gcd(x, y) == k的对数,这个问题在转化一下,转化成1 <= x <= lmtx / k,1 <= y <= lmty / k时x与y互质的对数.莫比乌斯反

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

分析:对于给出的n个询问,每次求有多少个数对(x,y),满足a≤x≤b,c≤y≤d,且gcd(x,y) = k,gcd(x,y)函数为x和y的最大公约数. 然后对于求这样单个的gcd(x,y)=k的,我们通常采用莫比乌斯反演 但是,时间复杂度是O(n*(n/k))的,当复杂度很坏的时候,当k=1时,退化到O(n^2),超时 然后进行分块优化,时间复杂度是O(n*sqrt(n)) #include<cstdio> #include<cstring> #include<queue

BZOJ2005: [Noi2010]能量采集 莫比乌斯反演的另一种方法——nlogn筛

分析:http://www.cnblogs.com/huhuuu/archive/2011/11/25/2263803.html 注:从这个题收获了两点 1,第一象限(x,y)到(0,0)的线段上整点的个数是gcd(x,y) 2,新学了一发求gcd(x,y)=k有多少对的姿势,已知0<x<=n,0<y<=m 令x=min(n,m),令f[i]代表gcd(x,y)=i的对数, 那么通过O(xlogx)的复杂度就可以得到f[1]到f[n](反着循环) 普通的容斥(即莫比乌斯反演)其实也