Kaosar və Sayma#12328

Kaosar və Sayma (Həll təhlili)

Problem Müəllifi:	AlKaosar Hüseyn
Hazırlayan:	Hasan Saleh (MathModel)
Redaktə edən:	Hasan Saleh (MathModel)

Həll

Biz $1 \leq a, b, c \leq n$ 1\le a,b,c\le n olan $(a, b, c)$ (a,b,c) tripletlərini sayırıq ki, bunlar arifmetik ardıcıllığın üç ardıcıl terminidir, cütlüklə fərqlidir və $g cd (a, b, c) = 1$ \gcd(a,b,c)=1 şərtini ödəyir.

$(a, b, c)$ (a,b,c) arifmetik ardıcıllıqda ardıcıl olduğuna görə, $x$ və $d \geq 1$ d\ge1 tam ədədləri mövcuddur ki,

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

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

Sərhədlər aşağıdakıları göstərir:

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

Qeyd edin ki,

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

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

çünki $g cd (x - d, x) = g cd (x, d)$ \gcd(x-d,x)=\gcd(x,d) və $g cd (x, x + d) = g cd (x, d)$ \gcd(x,x+d)=\gcd(x,d). Buna görə də $g cd (a, b, c) = 1$ \gcd(a,b,c)=1 şərti $g cd (x, d) = 1$ \gcd(x,d)=1 ilə eynidir.

Müəyyən $d$ üçün, $A = n - 2 d$ A=n-2d qoyaq. O zaman $x$ $A$ ardıcıl tam ədəd arasında dəyişir və etibarlı mərkəzlərin sayı

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

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

Möbius çevrilməsi ilə hesablanır. Bütün $d$ -lər üzrə birbaşa toplamaq çox yavaşdır, buna görə də Möbius funksiyasının prefiks cəmlərini istifadə edirik. Qoy

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

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

Biz $d$ -ni bloklar üzrə iterasiya edirik, burada həm

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

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

sabit qalır. Belə bir blok üçün $d \in [l, r]$ d\in[l,r], ümumi töhfə

(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).

Bu töhfələri bütün bloklar üzrə toplamaq $(x, d)$ cütlərinin sayını verir ki, $x - d, x, x + d$ x-d,x,x+d etibarlıdır və $g cd (x, d) = 1$ \gcd(x,d)=1.

Nəhayət, hər etibarlı cüt $(x, d)$ iki sıralı triplet yaradır,

(x - d, x, x + d) və (x + d, x, x - d),

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

beləliklə, nəticəni $2$ -yə vururuq.

Möbius funksiyası və onun prefiks cəmləri $O (n)$ vaxtda $1 0^{6}$ 10^6-ya qədər əvvəlcədən hesablanır. Hər bir test halı $O (n)$ O(\sqrt{n}) vaxtda işlənir ki, bu da məhdudiyyətləri asanlıqla ödəyir.

#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++