# Luogu p2522 [haoi2011] problem B solution

2022-05-15 07:28:50q779

# Luogu P2522 [HAOI2011]Problem b Answer key

The question ： For the given n n A asked , How many pairs are there at a time ( x , y ) (x,y) , Satisfy a ≤ x ≤ b a \le x \le b , c ≤ y ≤ d c \le y \le d , And gcd ⁡ ( x , y ) = k \gcd(x,y) = k , gcd ⁡ ( x , y ) \gcd(x,y) Function is x x and y y Maximum common divisor of .

One sentence question ：

seek
∑ i = a b ∑ j = c d [ gcd ⁡ ( i , j ) = k ] \sum_{i=a}^{b}\sum_{j=c}^{d}[\gcd(i,j)=k]
According to the principle of inclusion and exclusion , You may as well make
F ( n , m ) = ∑ i = 1 n ∑ j = 1 m [ gcd ⁡ ( i , j ) = k ] F(n,m) = \sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=k]
F ( b , d ) − F ( b , c − 1 ) − F ( a − 1 , d ) + F ( a − 1 , c − 1 ) F(b,d)-F(b,c-1)-F(a-1,d)+F(a-1,c-1)
Then push the persimmon
∑ i = 1 n ∑ j = 1 m [ gcd ⁡ ( i , j ) = k ] = ∑ i = 1 ⌊ n k ⌋ ∑ j = 1 ⌊ m k ⌋ [ gcd ⁡ ( i , j ) = 1 ] = ∑ i = 1 ⌊ n k ⌋ ∑ j = 1 ⌊ m k ⌋ ∑ d ∣ gcd ⁡ ( i , j ) μ ( d ) \begin{aligned} &\sum_{i=1}^{n}\sum_{j=1}^{m}[\gcd(i,j)=k] \\&=\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}[\gcd(i,j)=1] \\&=\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}\sum_{d\mid \gcd(i,j)}\mu(d) \end{aligned}
Consider transformation summation order , have to
∑ d = 1 min ⁡ ( ⌊ n k ⌋ , ⌊ m k ⌋ ) μ ( d ) ∑ i = 1 ⌊ n k ⌋ [ d ∣ i ] ∑ j = 1 ⌊ m k ⌋ [ d ∣ j ] \sum_{d=1}^{\min\left(\left\lfloor\frac{n}{k}\right\rfloor,\left\lfloor\frac{m}{k}\right\rfloor\right)}\mu(d)\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}[d\mid i]\sum_{j=1}^{\left\lfloor\frac{m}{k}\right\rfloor}[d\mid j]
according to 1 ∼ n 1\sim n in d d The multiples of are ⌊ n d ⌋ \left\lfloor\dfrac{n}{d}\right\rfloor individual ,

as well as ⌊ n k d ⌋ = ⌊ ⌊ n k ⌋ d ⌋ \left\lfloor\dfrac{n}{kd}\right\rfloor=\left\lfloor\dfrac{\left\lfloor\frac{n}{k}\right\rfloor}{d}\right\rfloor

Available
∑ d = 1 min ⁡ ( ⌊ n k ⌋ , ⌊ m k ⌋ ) μ ( d ) ⌊ n k d ⌋ ⌊ m k d ⌋ \sum_{d=1}^{\min\left(\left\lfloor\frac{n}{k}\right\rfloor,\left\lfloor\frac{m}{k}\right\rfloor\right)}\mu(d)\left\lfloor\dfrac{n}{kd}\right\rfloor\left\lfloor\dfrac{m}{kd}\right\rfloor
Then number theory is divided into blocks

Time complexity O ( N + Q n ) O(N+Q\sqrt{n})

Code ：

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
namespace FastIO
{

#define pc(a) putchar(a)
#define SIZ (int)(1e6+15)
char buf1[SIZ],*p1,*p2;
{

return p1==p2?EOF:*p1++;
}
{

char ch=gc();T x=0,f=1;
while(!isdigit(ch)){
if(ch=='-')f=-1;ch=gc();}
while(isdigit(ch)){
x=(x<<1)+(x<<3)+(ch^48);ch=gc();}
k=x*f;
}
template<typename T>void write(T k)
{

if(k<0){
k=-k;pc('-');}
static T stk;T top=0;
do{
stk[top++]=k%10,k/=10;}while(k);
while(top){
pc(stk[--top]+'0');}
}
}using namespace FastIO;
#define N (int)(5e4+14)
int prime[N],pcnt,mu[N],sum[N];
bool ck[N];
void Mobius()
{

mu=1;
for(int i=2; i<=N; i++)
{

if(!ck[i])
{

prime[++pcnt]=i;
mu[i]=-1;
}
for(int j=1; j<=pcnt&&i*prime[j]<=N; j++)
{

int pos=i*prime[j];
ck[pos]=1;
if(i%prime[j])
{

mu[pos]=-mu[i];
}else
{

mu[pos]=0;
break;
}
}
}
for(int i=1; i<=N; i++)
sum[i]+=sum[i-1]+mu[i];
}
int Q,a,b,c,d,k;
int solve(int n,int m)
{

int res=0;
n/=k;m/=k;
for(int l=1,r; l<=min(n,m); l=r+1)
{

r=min(n/(n/l),m/(m/l));
res+=(sum[r]-sum[l-1])*(n/l)*(m/l);
}
return res;
}
signed main()
{

// ios::sync_with_stdio(0);
// cin.tie(0);cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
while(Q--)
{