First, calculate the total number of trees without worrying about visibility.
Layer 1 has 5 trees.
Layer 2 has 10 trees.
.......
Layer $$$k$$$ has $$$5k$$$ trees.
What is the sum of $$$5k$$$ for $$$k=1$$$ to $$$n$$$?

A tree is "visible" if no other tree blocks the line of sight from the center. Think of a tree's position as a fraction along one side of the pentagon. A tree at layer $$$k$$$ and position $$$m$$$ (where $$$0 \le m \le k$$$) corresponds to the fraction $$$m/k$$$. When is the fraction $$$m/k$$$ "blocked" by a previous layer? It is blocked if the fraction can be simplified (e.g., $$$2/4$$$ is blocked by $$$1/2$$$).

A tree is visible only if its position fraction $$$m/k$$$ cannot be simplified. This happens when $$$\gcd(m, k) = 1$$$. The number of integers $$$m \lt k$$$ coprime to $$$k$$$ is given by Euler's Totient Function, $$$\phi(k)$$$. The vertices of the pentagon are special cases; handle them carefully. Total Hidden = Total Trees — Visible Trees.

We need to find the number of "hidden" trees in an orchard formed by concentric pentagons. Let's break the counting into two parts:

1. Calculate the Total number of trees.
2. Calculate the Visible number of trees.

1. Counting Total Trees
Layer $$$k$$$ is a regular pentagon. The problem states it has exactly 5 vertices and $$$5(k-1)$$$ additional trees on the edges.
Total trees in layer $$$k = 5 + 5(k-1) = 5k$$$.
Summing this from $$$1$$$ to $$$n$$$:

2. Counting Visible Trees

Consider one side of the pentagon on layer $$$k$$$. The trees on this side divide it into $$$k$$$ equal segments. We can assign each tree an index $$$m$$$ ($$$0 \le m \le k$$$) representing its position along the side. The relative position of a tree can be described by the fraction $$$\frac{m}{k}$$$.

A tree at layer $$$k$$$ with index $$$m$$$ is visible from the center if and only if there is no tree at the same relative position in any previous layer $$$k' \lt k$$$. Mathematically, this means the fraction $$$\frac{m}{k}$$$ must be irreducible.

Let's analyze the counts for each layer $$$k$$$:

• Vertices ($$$m=0$$$ and $$$m=k$$$): For $$$k=1$$$, the vertices are visible. For any $$$k \gt 1$$$, the vertices are hidden by the vertices of layer 1 (since $$$\gcd(k,k) \neq 1$$$ and $$$\gcd(0,k) \neq 1$$$).
• Edge Trees ($$$1 \le m \lt k$$$): The number of visible trees strictly on the edge of one side is the count of integers $$$m \in [1, k-1]$$$ such that $$$\gcd(m, k) = 1$$$. This is exactly the definition of Euler's Totient Function, $$$\phi(k)$$$.

Conclusion
The number of visible trees up to layer $$$n$$$ is $$$\sum_{k=1}^n 5 \phi(k)$$$.
The number of hidden trees is:

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

#define int long long

const int MAXN = 100005;
int phi[MAXN];
int prefix_phi[MAXN];

void precompute() {
    for (int i = 0; i < MAXN; i++) phi[i] = i;
    for (int i = 2; i < MAXN; i++) {
        if (phi[i] == i) {
            for (int j = i; j < MAXN; j += i)
                phi[j] -= phi[j] / i;
        }
    }
    prefix_phi[0] = 0;
    for (int i = 1; i < MAXN; i++) {
        prefix_phi[i] = prefix_phi[i-1] + phi[i];
    }
}

void solve() {
    int n;
    cin >> n;
    int total_trees = 5 * n * (n + 1) / 2;
    int visible_trees = 5 * prefix_phi[n];
    cout << total_trees - visible_trees << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    precompute();
    int t;
    cin >> t;
    while(t--) {
        solve();
    }
}

The core formula remains the same as the Easy Version:

However, since $$$n \le 10^9$$$, a simple linear loop is too slow.
You need an algorithm that runs faster than $$$O(n)$$$.

Let $$$S(n) = \sum_{i=1}^n \phi(i)$$$. We need to calculate $$$S(n)$$$ efficiently.
Recall the property of the Euler Totient function: $$$\sum_{d|n} \phi(d) = n$$$.
If we sum this identity over all $$$i$$$ from $$$1$$$ to $$$n$$$, we get:

Can you rearrange the left side to express $$$S(n)$$$ in terms of smaller values of $$$S$$$?

By changing the order of summation, we derive the recurrence relation known as the Du Jiao Sieve:

You can compute this using recursion with memoization.
1. For small $$$n$$$ (up to $$$\approx 2 \cdot 10^6$$$), precompute $$$S(n)$$$ using a linear sieve.
2. For large $$$n$$$, use the recursive formula and a hash map (or std::map).

Difference from Easy Version
In the hard version, $$$N$$$ can be up to $$$10^9$$$. The formula derived in the easy version is:

Explanation: Du Jiao Sieve

Let $$$S(n) = \sum_{i=1}^n \phi(i)$$$.
We know the property of Euler's totient function involving Dirichlet convolution:

Algorithm:

1. Precompute $$$\phi(i)$$$ and its prefix sums for small values (up to $$$K \approx N^{2/3}$$$, e.g., $$$2 \cdot 10^6$$$) using a linear sieve.
2. Recursion with Memoization: For values larger than $$$K$$$, use the formula above.
   • The summation $$$\sum_{g=2}^n S(\lfloor n/g \rfloor)$$$ can be computed efficiently using harmonic ranges (since $$$\lfloor n/g \rfloor$$$ takes limited distinct values).
   • Store computed results in a hash map (map or unordered_map) to avoid re-calculation.

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

#define int long long
const int MAXK = 2000005;

int phi[MAXK];
int prefix_phi[MAXK];
map<int, int> memo;

void precompute() {
    phi[1] = 1;
    vector<int> primes;
    static bool is_prime[MAXK];
    memset(is_prime, true, sizeof(is_prime));
    for (int i = 2; i < MAXK; i++) {
        if (is_prime[i]) {
            primes.push_back(i);
            phi[i] = i - 1;
        }
        for (int p : primes) {
            if (i * p >= MAXK) break;
            is_prime[i * p] = false;
            if (i % p == 0) {
                phi[i * p] = phi[i] * p;
                break;
            } else {
                phi[i * p] = phi[i] * (p - 1);
            }
        }
    }
    prefix_phi[0] = 0;
    for (int i = 1; i < MAXK; i++) {
        prefix_phi[i] = prefix_phi[i-1] + phi[i];
    }
}

int get_sum_phi(int n) {
    if (n < MAXK) return prefix_phi[n];
    if (memo.count(n)) return memo[n];
    int total = n * (n + 1) / 2;
    for (int l = 2, r; l <= n; l = r + 1) {
        r = n / (n / l);
        int count = (r - l + 1);
        total -= count * get_sum_phi(n / l);
    }
    return memo[n] = total;
}

void solve() {
    int n;
    cin >> n;
    int total_trees = 5 * n * (n + 1) / 2;
    int visible_trees = 5 * get_sum_phi(n);    
    cout << total_trees - visible_trees << endl;
}

signed main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    precompute();

    int t;
    cin >> t;
    while(t--) {
        solve();
    }
    return 0;
}

The answer is monotonic: if capacity $$$T$$$ works, any $$$T' \gt T$$$ works. Use Binary Search on the Answer.

Check Function: Greedily add people to the current trip. Start a new trip only when adding the next person would exceed the limit $$$T$$$.

Update Logic:

• If check(mid) is true, then mid is possible. Try to find a smaller answer: ans = mid, r = mid — 1.
• If check(mid) is false, we need more capacity: l = mid + 1.

The problem asks us to partition the array of people $$$m_1, m_2, \dots, m_N$$$ into at most $$$K$$$ contiguous subarrays (trips) such that the maximum tension required for any single trip is minimized. The tension for a group with total mass $$$M_{load}$$$ is given by $$$T = M_{load} \cdot G_{eff}$$$.

This is a classic "Minimize the Maximum" problem, which can often be solved using Binary Search on the Answer.

1. Monotonicity
Let's define a predicate function check(T) which returns true if it is possible to rescue all people in $$$\le K$$$ trips using a cable with tension rating $$$T$$$, and false otherwise.
If a tension rating $$$T$$$ is sufficient to rescue everyone, then any rating $$$T' \gt T$$$ is definitely sufficient as well. This monotonicity allows us to binary search for the minimum valid $$$T$$$.

2. The Check Function (Greedy Strategy)
For a fixed tension capacity $$$T_{limit}$$$, how do we determine the minimum number of trips required? Since the order of people is fixed, we can use a greedy approach:

• Start the first trip with the first person.
• Continue adding the next person in the queue to the current trip as long as the total tension does not exceed $$$T_{limit}$$$.
• If adding the next person would exceed $$$T_{limit}$$$, we must finalize the current trip and start a new one with that person.
• If any single individual requires a tension greater than $$$T_{limit}$$$ on their own ($$$m_i \cdot G_{eff} \gt T_{limit}$$$), then this $$$T_{limit}$$$ is immediately invalid.

After iterating through all people, if the number of trips used is less than or equal to $$$K$$$, then $$$T_{limit}$$$ is feasible.
We perform binary search within the range $$$[L, R]$$$. In each step, if check(mid) is true, we store mid as a potential answer and try smaller values ($$$R = mid - 1$$$). Otherwise, we look for larger values ($$$L = mid + 1$$$).

3. Time Complexity
The check function iterates through the array once, taking $$$O(N)$$$ time. The binary search runs for $$$O(\log(\sum m_i \cdot G_{eff}))$$$ iterations.
The total time complexity is $$$O(N \cdot \log(\text{Total Mass} \cdot G_{eff}))$$$, which fits comfortably within the time limit for $$$N \le 2 \cdot 10^5$$$.

#include<bits/stdc++.h>
#define int long long
#define pb push_back
using namespace std;
 
 
bool ok(int n,int k,int g,vector<int>&a,int m){
    int c=1,cur=0;
    for(int i=0;i<n;i++){
        int w=a[i]*g;
        if(w>m) return 0;
        if(cur+w<=m){
            cur+=w;
        }else{
            c++;
            cur=w;
        }
    }
    return c<=k;
}
 
 
int32_t main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
 
 
    int t;
    cin>>t;
    while(t--){
        int n,k,g;
        cin>>n>>k>>g;
 
 
        vector<int>a(n);
        int mx=0,sum=0;
        for(int i=0;i<n;i++){
            cin>>a[i];
            mx=max(mx,a[i]);
            sum+=a[i];
        }
 
 
        int l=mx*g,r=sum*g,ans=r;
        while(l<=r){
            int m=l+(r-l)/2;
            if(ok(n,k,g,a,m)){
                ans=m;
                r=m-1;
            }else{
                l=m+1;
            }
        }
        cout<<ans<<"\n";
    }
}

Jai wants to maximize the score, while Tarun wants to minimize it. Note : 1st position is always occupied by '(' and last position is occupied by ')' So, Jai will place biggest element in the very start if the array to maximise score Now since, Tarun wants to minimize the score will now place '(' in the second max element of the array

This concludes ans = 1st max — 1st min + 2nd max — 2nd min and so on.....

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(v) v.begin(), v.end()
#define loop(i, n) for (int i = 0; i < n; i++)
typedef vector<int> vi;
#define vin(a) for (int i = 0; i < (a).size(); i++) cin >> a[i];
#define sz(x) ((int)(x).size())

signed main() {
    ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    int t=1;
    // cin >> t;
    while (t--) {
        int n; cin >> n;
        vi a(n);
        vin(a);
        sort(all(a),greater<int>());
        int ans=0;
        for(int i=0;i<n;i+=2) ans+=(a[i]-a[i+1]);
        cout<<ans<<endl;
        
    }
    return 0;
}

Is the function $$$f(M) = \text{"Can we bake } M \text{ cookies?"}$$$ monotonic?

Binary Search

To bake $$$M$$$ cookies, the $$$i$$$-th ingredient requires a total of $$$M \cdot a_i$$$ grams.Aditya already possesses $$$b_i$$$ grams of the $$$i$$$-th ingredient. Therefore, the deficit (extra amount needed) for ingredient $$$i$$$ is:

Monotonicity:If we can bake $$$x$$$ cookies, we can also bake $$$x - 1$$$ cookies. The predicate function $$$f(x) = \text{"Can bake } x \text{ cookies?"}$$$ forms a monotonic pattern: $$$\text{TTTT}\dots\text{FFFF}\dots$$$. We simply binary search for the rightmost $$$\text{True}$$$ to get the maximum possible cookies.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define all(v) v.begin(), v.end()
#define loop(i, n) for (int i = 0; i < n; i++)
typedef vector<int> vi;
#define vin(a) for (int i = 0; i < (a).size(); i++) cin >> a[i];
#define pb push_back
#define sz(a) (int)a.size()
bool good(vi& a, vi& b, int mid, int k) {
    int n = sz(a);
    int dec = 0;
    loop(i, n) {
        int req = a[i] * mid;
        if (req > b[i]) {
            dec += (req &mdash; b[i]);
        }
        if (dec > k) return 0;
    }
    return 1;
}
signed main() {
    ios::sync_with_stdio(0); cin.tie(NULL); cout.tie(NULL);
    int t=1;
    // cin >> t;
    while (t--) {
        int n,k; cin >> n >> k;
        vi a(n),b(n);
        vin(a);vin(b);
        // Binary search -> ttttfff.. <- pattern
        int l=0,r=2e9;
        int ans=0;
        while(l<=r){
            int m = l+(r-l)/2;
            if(good(a,b,m,k)) ans=max(ans,m),l=m+1;
            else r=m-1;
        }
        cout<<ans<<endl;

    }
    return 0;
}

In 1 step, we can move the center by any distance $$$x \in (0, 2r]$$$ by choosing an appropriate rotation angle $$$\theta = 2 \arcsin\left(\frac{x}{2r}\right)$$$.Therefore, if $$$d \% 2r \neq 0$$$, we take $$$\lfloor \frac{d}{2r} \rfloor$$$ steps of length $$$2r$$$ plus 1 smaller step of length $$$d \bmod 2r$$$, totaling $$$\lceil \frac{d}{2r} \rceil$$$ steps.

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define loop(i, n) for (int i = 0; i < n; i++)
#define print_vec(a) for (int i = 0; i < a.size(); i++) cout << a[i] << " ";
#define endl '\n'
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(NULL);

    int r, x, y, xf, yf;
    cin >> r >> x >> y >> xf >> yf;
    int dx = xf - x;
    int dy = yf - y;
    
    int d2 = dx*dx + dy*dy;
    double d = sqrtl(d2);

    int ans = ceil(d/(2.0*r));
    
    cout << ans << "\n";


    return 0;
}

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void solve() {
    vector<long long> x(4);
    for (int i = 0; i < 4; ++i) {
        cin >> x[i];
    }
    sort(x.begin(), x.end());

    // S = x[3] = a + b + c
    long long a = x[3] - x[2];
    long long b = x[3] - x[1];
    long long c = x[3] - x[0];

    cout << a << " " << b << " " << c << "\n";
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    solve();
    
    return 0;
}

We construct the array starting with $$$P_1 = 1$$$. Each subsequent term $$$P_i$$$ ($$$1 \lt i \le N$$$) is formed by alternatingly applying step sizes (jumps) of $$$N$$$ and $$$N+2$$$:

$$$P_i = \vert{}N - P_{i-1}\vert{}$$$ if $$$i$$$ is odd,
$$$P_i = \vert{}(N + 2) - P_{i-1}\vert{}$$$ if $$$i$$$ is even.

Modulo $$$(N+1)$$$, notice that:
$$$N \equiv -1 \pmod{N+1}$$$
$$$N+2 \equiv +1 \pmod{N+1}$$$

2. Jump Sum Analysis ($$$L$$$):

For a contiguous block of length $$$k$$$, the jump sum $$$L_k$$$ alternates between terms of $$$N$$$ and $$$N+2$$$. The possible jump sums $$$L$$$ take two forms:

$$$\text{Type 1 (starts with } N \text{)}: N + (N+2) + N + (N+2) + \dots$$$
$$$\text{Type 2 (starts with } N+2 \text{)}: (N+2) + N + (N+2) + N + \dots$$$

For example, when $$$k = 3$$$:
$$$\text{Type 1: } N + (N+2) + N = 3N + 2$$$
$$$\text{Type 2: } (N+2) + N + (N+2) = 3N + 4$$$

Let L be the above value

3. Parity & Impossibility Proof:

Let's analyze $$$L$$$ and $$$N+1$$$ based on the parity of $$$N$$$:

It will be different in both the cases either n = even or odd which implies L%(N+1) can never be equals to zero

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vi vector<int>
#define loop(i, n) for (int i = 0; i < n; i++)
#define print_vec(a) for (int i = 0; i < a.size(); i++) cout << a[i] << " ";
#define endl '\n'
signed main() {
    int t=1;
    // cin >> t;
    while (t--) {
        int n; cin >> n;
        int s = (n*(n+1))/2;
        if(s%(n+1)){
            vi ans(n);
            ans[0] = 1;
            for(int i=1;i<n;i++){
                if(i&1) ans[i] = abs(n-ans[i-1]);
                else ans[i] = abs(n+2-ans[i-1]);
            }
            print_vec(ans);
            cout<<endl;
        }else cout<<-1<<endl;

    }
    return 0;
}