By contradiction, we can prove that for a connected undirected graph, each edge belongs to at most one cycle if and only if there are at most two non-intersect paths between any two vertices. In addition, the maximum flow problem and the minimum cut problem are equivalent, so we only need to consider how to cut some edges with the lowest sum of capacity so that the source vertex $$$s$$$ is not connected to the sink vertex $$$t$$$.

Let's take a look at the $$$s$$$-$$$t$$$ cut problem. If there are at least two edges in one cycle that are cut, we could figure out by adjusting that at most two of them should be cut, since there are at most two non-intersect paths between $$$s$$$ to $$$t$$$. In addition, if there are many cycles where some edges of each of them are cut, it can be known by adjusting and contradiction that only the edges of at most one cycle of them should be cut.

One observation is that if there is at least one edge in some cycle should be cut in the best solution of the minimum cut problem, there must be two edges in that cycle need to be cut, one of which is the edge with the smallest capacity in that cycle. Hence, we can remove the edge with the smallest capacity in each cycle and add its capacity to the other edges in the cycle, and the maximum flow between any two vertices will not change in value.

The modified graph forms a tree. If we add edges to an empty graph in descending order of its capacity, we can determine $$$\mathrm{flow}(s, t) = w$$$ $$$(s \in S, t \in T)$$$ for the two sets of vertices $$$S$$$ and $$$T$$$ that are firstly connected after joining the edge of capacity $$$w$$$. Just maintain these sets of vertices by the disjoint set union, count in each set the number of vertices whose bit in some fixed position are $$$1$$$, and then it is easy to calculate the answer by enumerating each bit. Time complexity is $$$\mathcal{O}(m \log n)$$$.

Note that $$$\mathrm{flow}(s, t)$$$ can be $$$2 \times 10^9$$$, which means the answer may exceed $$$2^{63}$$$. To reach the peak value, we may just construct a circle with edges of the same weight $$$10^9$$$.

For each permutation of positions, the minimum number of swaps equals to $$$n$$$ minus the number of disjoint cycles in the permutation.

We can solve the problem by enumerating all the $$$n$$$-permutations. For each permutation, we only need to check if it can be reached within $$$k$$$ swaps as swapping the same position is permitted.

Time complexity is expected to be $$$\mathcal{O}(m!)$$$, where $$$m = \left \lfloor \log_{10} n \right \rfloor + 1$$$. In order to achieve that, we can maintain some information about chains and cycles so that we can modify and retrieve efficiently during searching and backtracking.

For each permutation of positions, the minimum number of swaps equals to $$$n$$$ minus the number of disjoint cycles in the permutation.

We can precalculate the minimum number of steps to obtain a permutation from the original one, and then enumerate and check. Time complexity is $$$\mathcal{O}\left(\sum_{i = 1}^{9}{(i \cdot i!)} + T m!\right)$$$, where $$$m = \left \lfloor \log_{10} n \right \rfloor + 1$$$.

Some solution cannot handle the case $$$n = 10^9$$$, but it can be solved by hand.

As we know, Möbius inversion formula can be expressed as

where $$$\mu$$$ is the Möbius function and the sums extend to all positive divisors $$$d$$$ of $$$n$$$.

Similarly, we can obtain the following formula.

If we apply this formula, the problem can be solved in $$$\mathcal{O}(2^{\omega(n)} n)$$$, where $$$\omega(n)$$$ means the number of distinct prime factors of $$$n$$$. To prove that, you need to know what the Möbius function is and observe that $$$f(n)$$$ in this problem is a polynomial with only two non-zero terms.

By the way, $$$\omega(n) \leq 6$$$ when $$$n \leq 10^5$$$, because $$$2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 = 510510$$$.

Q: Why does Fast Fourier Transform get a verdict of TLE? It seems $$$\log n \approx 2^{\omega(n)}$$$.

A: FFT implies big constant factor. Also, the above solution does not require floating point operation.