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

Həll

Gəlin \gcd(i,j)=1 olduğu halda i<j cütlərini sıralı şəkildə nəzərdən keçirək. Bu, bizə sayları çox saymağı önləməyə kömək edir, çünki sırasız cütlər çox sayılır. Hər hansı bir $i$ üçün, $j$-nin $i$-dən kiçik olan ədədlərinin sayını bilmək istəyirik ki, \gcd(i,j)=1 olsun, bu da $\phi (i)$ Euler Totient Funksiyası ilə eynidir. Bu yolla $(i,j)$ cütünü iki dəfə saymayacağıq, buna görə də hər bir ədəd üçün dəyərləri ayrıca toplaya bilərik. Rəsmi olaraq

Lakin, əgər qrafi müşahidə etsəniz, artıq qrafi düzəldən $n$ xətt var. Buna görə də

İfadə belədir

Lakin, \varphi(1)=1 sayını saydığınızı unutmayın, onu istisna etməliyik, buna görə də son ifadə

1 \le x \le 2 \cdot 10^5 üçün $\phi (x)$-i əvvəlcədən hesablayaraq, \mathcal{O}(\sum n) əldə edirik, lakin problem bəyanatından $\sum n$ məhdud deyil, buna görə də hesablamanı prefiks cəmi ilə sürətləndirə bilərik.

İndi test hallarını $\mathcal{O}(1)$ vaxtında cavablandıra bilərik!.

Komplekslik \mathcal{O}(N\log \log N), burada 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();
}