【bzoj2820】YY的GCD

2015年1月12日5,1646

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

Source

 假定n<m
\[\sum_{isprime(p)}\sum_{a=1}^n\sum_{b=1}^mgcd(a,b)==p\]
\[\sum_{isprime(p)}\sum_{a=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\sum_{b=1}^{\left \lfloor \frac{m}{p} \right \rfloor}gcd(a,b)==1\]
\[\sum_{isprime(p)}\sum_{a=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\sum_{b=1}^{\left \lfloor \frac{m}{p} \right \rfloor}\sum_{d|gcd(a,b)}\mu(d)\]
\[\sum_{isprime(p)}\sum_{a=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\sum_{b=1}^{\left \lfloor \frac{m}{p} \right \rfloor}\sum_{d|a \land d|b}\mu(d)\]
\[\sum_{isprime(p)}\sum_{d=1}^{\left \lfloor \frac{n}{p} \right \rfloor}\mu(d){\left \lfloor \frac{n}{pd} \right \rfloor}{\left \lfloor \frac{m}{pd} \right \rfloor}\]
将pd设为k
\[\sum_{k=1}^{n}\sum_{isprime(p) \land p|k}\mu(\frac{k}{p}){\left \lfloor \frac{n}{k} \right \rfloor}{\left \lfloor \frac{m}{k} \right \rfloor}\]
\[\sum_{k=1}^{n}F(k){\left \lfloor \frac{n}{k} \right \rfloor}{\left \lfloor \frac{m}{k} \right \rfloor}\]
可以线筛预处理F,或者暴力枚举质数(这个复杂度我不能确定),按照素数粗略个数n/logn以及调和级数求和nlogn来看暴力的复杂度接近On
处理完F以后就是喜闻乐见的下底函数分块

 

 

  • DYDXH2015年8月5日 下午8:22 回复

    话说..请问…第四个公式是怎么变到第五个公式的….

    #1  
    • Duyixian2016年6月28日 上午9:40 回复

      就是把莫比乌斯函数提前啊OwO

      #11
  • Duyixian2016年6月28日 上午10:05 回复

    黄学长,哪个预处理其实不用O(nlogn),可以直接在线性筛上加两句话,达到O(n)…OwO

    #2  
  • PSI2017年6月5日 下午8:22 回复

    楼上的、、
    线筛不能处理所有质因数的mu和,只能拉出来
    如 42=2*3*7 2可以和21计算出 统计2的贡献 3可以和14计算出 统计3的贡献 但是7和6中的7也应该有贡献,但7不会和6算,6也不会和7算
    所以线筛并不能统计出每个包含质因数的两因子相乘的情况、、
    如有错请轻喷 (⊙ω⊙)

    #3  
  • DZYO2017年7月23日 下午5:47 回复

    学长怎么分析出O(n)的,难道不是总共更新(n/1+n/2+n/3+n/4+…+n/n)=nlogn次?

    #4