Dolphins#3213
Spring… Rabbits rejoice in the sunshine, the sky is soft and kind, flowers are blooming, and dolphins have returned from warm countries.
Indeed, for rabbits, dolphins are the main symbols of spring. They sing beautifully, fly gracefully, and twirl delightfully. This behavior brings joy and smiles to almost everyone. Almost… Researchers from the Institute of Dolphin Population Control in the treetops of Rabbitland are given a lot of work during this cheerful time. They must manage entire flocks of dolphins. But they hope that we will design an algorithm to forecast the dolphin population in the treetops.
Thus, you are to write a program that determines the likely positions of dolphins. You will be given the positions of dolphins initially. In total, trees must be managed. Each dolphin starts at the top of some tree. Each second, a dolphin, with equal probability, can fly to any tree with a number that is coprime with the number of the tree where it is currently sitting (i.e., their greatest common divisor is ), or it can stay at its current tree. Thus, if there are trees and a dolphin is on tree number , then the events "the dolphin will be on tree number (or , , , ) in one second" are equally probable.
To check the correctness of your algorithm, output the sum of the mathematical expectations for the number of dolphins on the trees after seconds. That is, if m_1, m_2, ..., m_M are the mathematical expectations of the number of dolphins on the first, second, ..., and -th trees respectively, you need to compute
The first line contains three integers separated by spaces: , , (1 \leq N, M, T \leq 1000) — the number of dolphins, the number of trees, and the number of seconds to simulate. The second line contains integers separated by spaces, indicating the initial positions of the dolphins (trees are numbered from to ).
Print the result with exactly digits after the decimal point.
Example 1