Kaosar and Counting#12328

Kaosar and Counting (Талдоо)

Problem Author:	AlKaosar Hussain
Prepared by:	Hasan Saleh (MathModel)
Edited by:	Hasan Saleh (MathModel)

Solution

We count triplets $(a, b, c)$ (a,b,c) with $1 \leq a, b, c \leq n$ 1\le a,b,c\le n that are three consecutive terms of an arithmetic progression, pairwise distinct, and satisfy $g cd (a, b, c) = 1$ \gcd(a,b,c)=1.

Since $(a, b, c)$ (a,b,c) are consecutive in an arithmetic progression, there exist integers $x$ and $d \geq 1$ d\ge1 such that

(a, b, c) = (x - d, x, x + d) .

(a,b,c)=(x-d,x,x+d).

The bounds imply

d + 1 \leq x \leq n - d, d \leq \frac{n - 1}{2} .

d+1\le x\le n-d, \qquad d\le \frac{n-1}{2}.

Observe that

g cd (x - d, x, x + d) = g cd (x, d),

\gcd(x-d,x,x+d)=\gcd(x,d),

because $g cd (x - d, x) = g cd (x, d)$ \gcd(x-d,x)=\gcd(x,d) and $g cd (x, x + d) = g cd (x, d)$ \gcd(x,x+d)=\gcd(x,d). Hence the condition $g cd (a, b, c) = 1$ \gcd(a,b,c)=1 is equivalent to $g cd (x, d) = 1$ \gcd(x,d)=1.

For a fixed $d$ , let $A = n - 2 d$ A=n-2d. Then $x$ ranges over $A$ consecutive integers, and the number of valid centers is

k ∣ d \sum μ (k) ⌊ \frac{A}{k} ⌋,

\sum_{k\mid d}\mu(k)\left\lfloor\frac{A}{k}\right\rfloor,

by Möbius inversion. Summing over all $d$ directly is too slow, so we use prefix sums of the Möbius function. Let

M (t) = i = 1 \sum t μ (i) .

M(t)=\sum_{i=1}^{t}\mu(i).

We iterate $d$ in blocks where both

A = ⌊ \frac{n}{d} ⌋ and J = ⌊ \frac{n - 1}{2 d} ⌋

A=\left\lfloor\frac{n}{d}\right\rfloor \quad\text{and}\quad J=\left\lfloor\frac{n-1}{2d}\right\rfloor

remain constant. For such a block $d \in [l, r]$ d\in[l,r], the total contribution equals

(J A - J (J + 1)) \cdot (M (r) - M (l - 1)) .

\big(JA-J(J+1)\big)\cdot\big(M(r)-M(l-1)\big).

Summing these contributions over all blocks gives the number of pairs $(x, d)$ with $x - d, x, x + d$ x-d,x,x+d valid and $g cd (x, d) = 1$ \gcd(x,d)=1.

Finally, each valid pair $(x, d)$ produces two ordered triplets,

(x - d, x, x + d) and (x + d, x, x - d),

(x-d,x,x+d)\quad\text{and}\quad(x+d,x,x-d),

so we multiply the result by $2$ .

The Möbius function and its prefix sums are precomputed up to $1 0^{6}$ 10^6 in $O (n)$ time. Each test case is processed in $O (n)$ O(\sqrt{n}), which easily satisfies the constraints.

#include <bits/stdc++.h>
using namespace std;
#define int long long

const int N=1000000;

int mu[N+1],pm[N+1];
int p[N],pc;
bool c[N+1];

inline int M(int x){
    if(x<=0)return 0;
    return pm[x];
}

void precalc(){
    mu[1]=1;
    for(int i=2;i<=N;i++){
        if(!c[i]){
            p[pc++]=i;
            mu[i]=-1;
        }
        for(int j=0;j<pc;j++){
            int x=p[j];
            if(i*x>N)break;
            c[i*x]=1;
            if(i%x==0){
                mu[i*x]=0;
                break;
            }
            mu[i*x]=-mu[i];
        }
    }
    for(int i=1;i<=N;i++)pm[i]=pm[i-1]+mu[i];
}

void solve(){
    int n;cin>>n;
    int lim=(n-1)/2;
    int ans=0;
    for(int l=1;l<=lim;){
        int A=n/l;
        int J=(n-1)/(2*l);
        int r=min({n/A,(n-1)/(2*J),lim});
        ans+=(J*A-J*(J+1))*(M(r)-M(l-1));
        l=r+1;
    }
    cout<<(ans*2)<<"\n";
}

signed main(){
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    precalc();
    int t=1;cin>>t;
    while(t--)solve();
}

C++