Каосар і Діагоналі (Розбір)

Рішення

Розглянемо впорядкований спосіб пар i<j, де \gcd(i,j)=1, це допомагає уникнути подвійного підрахунку, оскільки невпорядковані пари підраховуються двічі. Для деякого $i$ ми хочемо знати, скільки цілих чисел $j$, менших за нього, таких що \gcd(i,j)=1, це еквівалентно $\phi (i)$ Функція Ейлера. Оскільки ми не будемо підраховувати пару $(i,j)$ двічі таким чином, ми можемо підсумувати значення для кожного цілого числа окремо, формально

Однак, якщо ви помітили графік, там вже є $n$ ліній, що формують графік. Отже,

Тому вираз буде

Однак зверніть увагу, що ви підраховуєте \varphi(1)=1, тому ми повинні виключити його, отже, фінальний вираз буде

Підрахувавши $\phi (x)$ для всіх 1 \le x \le 2 \cdot 10^5, ми отримуємо \mathcal{O}(\sum n), однак з умови задачі $\sum n$ не обмежена, тому ми можемо прискорити обчислення за допомогою префіксної суми.

Тепер ми можемо відповідати на набори входних даних за $\mathcal{O}(1)$ часу!.

Складність \mathcal{O}(N\log \log N), де N=2 \cdot 10^5.

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>
using namespace std;
using namespace __gnu_pbds;

#define int long long
template<class T> using oset=tree<T,null_type,less<T>,rb_tree_tag,tree_order_statistics_node_update>;

const int N=200000;
int phi[N+1];
vector<int>sum={0};

void solve(){
    int n;cin>>n;
    cout<<sum[n]-n-1<<"\n";
}

signed main(){
    for(int i=1;i<=N;i++)phi[i]=i;
    for (int i=2;i<=N;i++) {
        if (phi[i]==i) {
            for (int j=i;j<=N;j+=i)
                phi[j]-=phi[j]/i;
        }
    }
    int cur=0LL;
    for(int i=1;i<=N;i++){
        cur+=phi[i];
        sum.push_back(cur);
    }
    int t=1;cin>>t;
    while(t--) solve();
}