editorial done on request

and as usual, the benq editorial was mathy and didn't explain much

i can't explain this problem succintly, so it's best if you just go read the thing for yourself

this is one of those "wth" problems where you have literally no clue how to do it except for the brutiest of brute forces

but anyways after some malding it's possible for us to figure out that each permutation can be decomposed into a series of "cycles"

take for example this permutation: ```py [1, 3, 2, 5, 4] ``` then we can take cows 4 & 5, put them in their own group, and do the same for cows 1-3

each step, the cows in each group rotate, and it takes `the_size_of_their_group` steps
for the cows to go back to their original position

so the amt of time it takes for this permutation to come together is just
the LCM (least common multiple) of all the group sizes

so this problem can be transformed into the following:

given a number `n`

what's the sum over all distinct values of the LCMs of all partitions of `n`?

one tiny problem

the number of partitions of a `n` increases EXPONENTIALLY as `n` increases

good thing we only have to count the # of distinct LCMs

because after some more malding, it's possible to notice
that there's a specific section of all the partitions that
can represent the entire class of LCMs

idk bout you, but when i think of LCMs i think of prime factors

so how about we think about (the transformed) problem from the perspective
of prime numbers?

so let's set our `n` to a medium number, say, `50`

let's also do a random partition, such as
```py
[36, 9, 7, 1]
```
the LCM of this is \( 36 \cdot 7 = 252 \)

but here's the thing

this partition here, consisting entirely of just prime powers:
```py
[4, 9, 7, 1, 1, (26 more 1's), 1, 1]
```
achieves the same LCM with less space taken up! (the 1's can be considered empty space to a certain degree)

so i have a proposal i'd like to make

no matterWHATpartition we use, there is always going to be a partition consistingonlyof prime powers and 1's that has the same LCM

not really sure how to prove this, it just comes kinda intuitively tbh

so just trust me on this

i mean you can just transform all partitions into a partition only of prime powers
with the same LCM by just taking the prime factors and putting them in

there's always going to be enough space btw trust me

ok so now we know that we only have to check prime powers

but here's the kicker

that observation was only like 1/3 of the actual problem

we now have to actually implement it

btw this problem is dp if you didn't know, to get this you have to just kinda feel it in your bones or look @ some problem tags

so uh let's let
```
dp[i] = sum of all the LCMs of the partitions whose relevant prime powers sum up to i
```
(for example, `[64, 9, 1, 1, 1]`

would
have its LCM accounted for in `dp[73]`)

of course, we aren't just going to be only using this array- we're going to go through all prime powers and update the array accordingly

now comes the part of actually figuring out the relation

say we were to add a random prime power \( p^x \) to some partition.
how would this affect the LCM given that we know the partition knows
nothing of \( p \) initially?

well, it would just multiply the LCM by \( p^x \)!

so i guess for each prime power, we just go through all the existing elements of `dp`, and then multiply it by said prime power and then go?

hm

yeah that should work, since we know that none of the partitions we've considered
have whatever current prime power we're considering

so yeah that's it, the code follows:

```java import java.io.*; import java.math.BigInteger; import java.util.*; /** * 2020 us open gold * also this is slow mostly bc of the bigintegers * if you want like super speed, just switch to longs and do everything mod the mod idk */ public class Exercise { public static void main(String[] args) throws IOException { StringTokenizer initial = new StringTokenizer( new BufferedReader(new FileReader("exercise.in")).readLine() ); int cowNum = Integer.parseInt(initial.nextToken()); BigInteger mod = new BigInteger(initial.nextToken()); // the sum of all the LCMs of the prime powers that sum to i (the array index) BigInteger[] totalWithSum = new BigInteger[cowNum + 1]; Arrays.fill(totalWithSum, BigInteger.ZERO); totalWithSum[0] = new BigInteger("1"); for (int i = 2; i <= cowNum; i++) { if (!prime(i)) { continue; } /* * keep another array where we store the updates so the prime * powers of a single number don't go harrassing each other */ BigInteger[] updatedTotal = totalWithSum.clone(); for (int p = i; p <= cowNum; p *= i) { // go through all prime powers for (int from = 0; from + p <= cowNum; from++) { updatedTotal[from + p] = updatedTotal[from + p].add( totalWithSum[from].multiply(new BigInteger(String.valueOf(p))) ); } } totalWithSum = updatedTotal; } BigInteger total = BigInteger.ZERO; for (BigInteger prod : totalWithSum) { total = total.add(prod); } total = total.mod(mod); PrintWriter written = new PrintWriter("exercise.out"); written.println(total); written.close(); } // sauce: https://www.geeksforgeeks.org/primality-test-set-1-introduction-and-school-method private static boolean prime(int n) { if (n <= 1) return false; if (n <= 3) return true; if (n % 2 == 0 || n % 3 == 0) return false; for (int i = 5; i * i <= n; i = i + 6) if (n % i == 0 || n % (i + 2) == 0) return false; return true; } } ```