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";
    }
}

Analyze the bitwise difference for small numbers manually.
$$$1 (01) \to 2 (10)$$$: Difference is 2 bits. (Ends in 1 one)
$$$3 (011) \to 4 (100)$$$: Difference is 3 bits. (Ends in 2 ones)
$$$7 (0111) \to 8 (1000)$$$: Difference is 4 bits. (Ends in 3 ones)

Do you see the relationship between the number of trailing ones and the bitwise difference?

If a number ends in exactly $$$p$$$ ones, adding 1 will flip those $$$p$$$ ones to zeros and flip the next zero to a one. The total change is $$$p+1$$$ bits.
To get a difference of exactly $$$k$$$, the number must end in exactly $$$k-1$$$ ones.

We need to count numbers $$$i \lt n$$$ that end in the pattern ...011...1 (with $$$k-1$$$ ones).
This pattern repeats every $$$2^k$$$ numbers.

We need to count how many integers $$$i$$$ in the range $$$[0, n-1]$$$ change exactly $$$k$$$ bits when incremented to $$$i+1$$$.

Mathematical Derivation

1. The Bitwise Property
When we add $$$1$$$ to an integer $$$i$$$, the number of bits that flip is determined by the number of trailing ones in $$$i$$$.
Specifically, if $$$i$$$ ends with $$$z$$$ ones (e.g., $$$\dots 0\underbrace{11\dots1}_{z}$$$), adding $$$1$$$ will flip all those $$$z$$$ ones to zeros, and flip the zero immediately to their left to a one.
The total bits changed (the bitwise difference) is $$$z + 1$$$.

2. The Condition
We are given that the difference is $$$k$$$.

3. The Formula
This pattern repeats with a period of $$$2^k$$$. The first number satisfying this is $$$2^{k-1} - 1$$$.
To count how many such numbers exist strictly less than $$$n$$$, we can use the direct formula for counting arithmetic progressions:

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

void solve() {
    int n, k;
    cin >> n >> k;
    if (k == 0) {
        cout << 0 << endl;
        return;
    }
    int ans = (n + (1ll << (k - 1))) >> k;
    cout << ans << endl;
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    
    int t;
    cin >> t;
    while (t--) {
        solve();
    }
    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 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 — 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;
}