# 「BZOJ2820」YY的GCD

2015年1月12日8,4378

## Description

kAc这种傻×必然不会了，于是向你来请教……

## Output

T行，每行一个整数表示第i组数据的结果

2
10 10
100 100

30
2791

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}$

$\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}$

ranwen
DZYO

RandomWalker

cnt不是n/logn级别吗

Duyixian

Duyixian