The square root of $$$x^2$$$ when $$$x$$$ is an integer is also an integer. We can use this and print $$$1^2, \ 2^2, \ 3^2, \dots, n^2$$$

n = int(input())
for i in range(1, n + 1):
  print(i * i, end = ' ')

$$$A = a \cdot b \to a = \frac{A}{b}$$$

#include <bits/stdc++.h>
using namespace std;
int main() {
  int A, b; cin >> A >> b;
  cout << A / b;
}

To find $$$y$$$ we can find the first prime factor of $$$x$$$ by checking each integer from $$$2$$$ to $$$\sqrt{x}$$$, and if there aren't any divisors of $$$x$$$ in this range, then the answer is $$$x$$$.

Why this works? $$$y$$$ shares exactly one prime factor with $$$x$$$ ( itself ), and the first divisor of any integer $$$\neq 1$$$ is a prime.

#include <bits/stdc++.h>

using namespace std;

int main() {
    int x; cin >> x;
    
    for (int i = 2; i * i <= x; i++) {
        if (x % i == 0) {
            cout << i << "\n";
            return 0;
        }
    }
    cout << x << "\n";
}

We can express $$$x = l \cdot a + r \cdot b$$$ and $$$y = l \cdot b + r \cdot a$$$ then:

Then we have to check:

• is $$$x + y$$$ divisible by $$$a + b$$$
• is $$$x - y$$$ divisible by $$$a - b$$$
• is $$$d + c$$$ divisible by $$$2$$$
• is $$$d - c$$$ divisible by $$$2$$$
• $$$l \ge 0$$$ and $$$r \ge 0$$$

If all conditions are met, the answer is $$$l + r = d$$$. Otherwise, output $$$-1$$$.

#include <bits/stdc++.h>

using namespace std;

int main() {
  int t;
  cin >> t;
  while (t--) {
    int x, y, a, b;
    cin >> x >> y >> a >> b;
    if (x > y) swap(x, y);
    if (a > b) swap(a, b);

    if ((x + y) % (a + b) != 0 or
        (a == b and (x % a != 0 or y % a != 0) or (y - x) % (b - a) != 0)) {
      cout << "-1\n";
      continue;
    }
    int c = (x + y) / (a + b);
    int d = (y - x) / (b - a);
    int l = (c + d) / 2;
    int r = (c - d) / 2;
    if (l < 0 or r < 0 or (c + d) % 2 == 1 or (c - d) % 2 == 1) {
      cout << "-1\n";
      continue;
    }
    cout << (x + y) / (a + b) << "\n";
  }
}

We can use a DP approach. Let $$$dp[i][j]$$$ mean if we consider a subset of the first $$$i$$$ coins what is the maximum number of different coin types we can use to make $$$j$$$. Then $$$dp[0][0] = 0$$$ and $$$dp[i][j] = -\infty$$$.

For each type $$$i$$$ and amount $$$j$$$ we have two choices

1. Dont use type $$$i$$$: $$$dp[i][j] = dp[i - 1][j]$$$

2. Use coin type $$$i$$$:

   • We need to use at least one coin of type $$$j$$$ so we subtract $$$d[i]$$$ from $$$j$$$.
   • Then $$$dp[i][j] = \max (dp[i - 1][j - d[i]] + 1, \ dp[i][j - d[i]])$$$.

So $$$dp[i][j] = \max (dp[i - 1][j], \ dp[i - 1][j - d[i]] + 1, \ dp[i][j - d[i]])$$$. The answer is $$$dp[n][x]$$$ if it isn't $$$-\infty$$$ or $$$-1$$$ else.

#include <bits/stdc++.h>

using namespace std;

#define vec vector

int main()
{
  int n, x;
  cin >> n >> x;

  vec<vec<int>> dp(n + 1, vec<int>(x + 1, INT_MIN));
  vec<int> d(n);
  for (int i = 0; i < n; i++)
    cin >> d[i];
  dp[0][0] = 0;
  for (int i = 1; i <= n; i++)
  {
    for (int j = d[i - 1]; j <= x; j++)
    {
      dp[i][j] = max(dp[i - 1][j - d[i - 1]] + 1, dp[i][j - d[i - 1]]);
    }
    for (int j = 0; j <= x; j++)
      dp[i][j] = max(dp[i][j], dp[i - 1][j]);
  }
  if (dp[n][x] < 0)
    cout << -1 << "\n";
  else
    cout << dp[n][x] << "\n";
}

Key Observation: If vertex $$$u$$$ meets $$$v$$$ at any point, it will always be equal to $$$v$$$ from that point onward (since the graph is functional — each vertex has exactly one outgoing edge). So if we simulate at least $$$n$$$ steps and check if they're equal, we'll know if they ever met.

How to simulate at least $$$n$$$ steps fast? We can use jump pointers to simulate $$$\ge n$$$ steps in O(1) time. Let $$$jmp[v][k]$$$ = the vertex we reach after taking $$$2^k$$$ steps starting from $$$v$$$. - Base case: $$$jmp[v][0] = a[v]$$$ (the direct neighbor of $$$v$$$) - Recurrence: $$$jmp[v][k] = jmp[jmp[v][k-1]][k-1]$$$ This works because taking $$$2^k$$$ steps = taking $$$2^{k-1}$$$ steps, then taking another $$$2^{k-1}$$$ steps.

To answer each query: Find the smallest $$$k$$$ such that $$$2^k \ge n$$$. Then check if $$$jmp[u][k]$$$ == $$$jmp[v][k]$$$. If yes, they will meet, otherwise, they will never meet.

#include <bits/stdc++.h>

using namespace std;
#define vec vector

const int K = 20;
int main()
{
  int n;
  cin >> n;
  vec<int> next(n);
  vec<vec<int>> jmp(K, vec<int>(n));

  for (int i = 0; i < n; i++)
  {
    cin >> next[i];
    jmp[0][i] = next[i] - 1;
  }

  for (int k = 1; k < K; k++)
  {
    for (int i = 0; i < n; i++)
    {
      jmp[k][i] = jmp[k - 1][jmp[k - 1][i]];
    }
  }

  int q;
  cin >> q;
  while (q--)
  {
    int a, b;
    cin >> a >> b;
    a--;
    b--;
    if (jmp[K - 1][a] == jmp[K - 1][b])
    {
      cout << "YES\n";
    }
    else
    {
      cout << "NO\n";
    }
  }
}

const int MAXN = 100000;
const int K = 10;
int jmp[K][MAXN];
void init(vector<int> parent) {
    for (int i = 0; i < parent.size(); i++) {
        jmp[0][i] = parent[i];
    }
    
    for (int i = 1; i < K; i++) {
        for (int j = 0; j < MAXN; j++) {
             jmp[i][j] = jmp[i - 1][jmp[i - 1][jmp[i - 1][jmp[i - 1][j]]]];
        }
    }
}

int jump(int v, int x) {
    int i = 0;
    while (x >= 1) {
        for (int o = 0; o < x % 4; o++) {
              v = jmp[i][v];
        }
        x /= 4;
        i++;
    }
    return v;
}