Каосар і підрахунок#12328

Каосар і підрахунок (Розбір)

Автор проблеми:	AlKaosar Hussain
Підготовлено:	Hasan Saleh (MathModel)
Редаговано:	Hasan Saleh (MathModel)

Рішення

Ми підраховуємо трійки $(a, b, c)$ (a,b,c) з $1 \leq a, b, c \leq n$ 1\le a,b,c\le n, які є трьома послідовними членами арифметичної прогресії, парно різними і задовольняють $g cd (a, b, c) = 1$ \gcd(a,b,c)=1.

Оскільки $(a, b, c)$ (a,b,c) є послідовними в арифметичній прогресії, існують цілі числа $x$ і $d \geq 1$ d\ge1, такі що

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

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

Обмеження вказують на те, що

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

Зверніть увагу, що

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

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

оскільки $g cd (x - d, x) = g cd (x, d)$ \gcd(x-d,x)=\gcd(x,d) і $g cd (x, x + d) = g cd (x, d)$ \gcd(x,x+d)=\gcd(x,d). Отже, умова $g cd (a, b, c) = 1$ \gcd(a,b,c)=1 еквівалентна $g cd (x, d) = 1$ \gcd(x,d)=1.

Для фіксованого $d$ нехай $A = n - 2 d$ A=n-2d. Тоді $x$ змінюється по $A$ послідовним цілим числам, і кількість дійсних центрів дорівнює

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

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

за допомогою обернення Мебіуса. Пряме підсумовування по всіх $d$ занадто повільне, тому ми використовуємо префіксні суми функції Мебіуса. Нехай

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

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

Ми ітеруємо $d$ в блоках, де обидва

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

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

залишаються постійними. Для такого блоку $d \in [l, r]$ d\in[l,r] загальний внесок дорівнює

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

Сумування цих внесків по всіх блоках дає кількість пар $(x, d)$ з дійсними $x - d, x, x + d$ x-d,x,x+d і $g cd (x, d) = 1$ \gcd(x,d)=1.

Нарешті, кожна дійсна пара $(x, d)$ генерує дві впорядковані трійки,

(x - d, x, x + d) та (x + d, x, x - d),

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

тому ми множимо результат на $2$ .

Функція Мебіуса та її префіксні суми попередньо обчислюються до $1 0^{6}$ 10^6 за $O (n)$ часу. Кожен тестовий випадок обробляється за $O (n)$ O(\sqrt{n}), що легко задовольняє обмеження.

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