Vladivostok's Sea of Stones: Maximizing Skipping Stones with Different Forces

"In Vika's hometown, Vladivostok, there is a beautiful sea. Often you can see kids skimming stones. This is the process of throwing a stone into the sea at a small angle, causing it to fly far and bounce several times off the water surface. \n\nVika has skimmed stones many times and knows that if you throw a stone from the shore perpendicular to the coastline with a force of \t\n\tf , it will first touch the water at a distance of \t\n\tf from the shore, then bounce off and touch the water again at a distance of \t\n\t−1f−1 from the previous point of contact. The stone will continue to fly in a straight line, reducing the distances between the points where it touches the water, until it falls into the sea. \n\nFormally, the points at which the stone touches the water surface will have the following coordinates: \t\n\tf , \t\n\t+(f−1)f+(f−1) , \t\n\t+(f−1)+(f−2)f+(f−1)+(f−2) , ... , \t\n\t+(f−1)+(f−2)+…+1f+(f−1)+(f−2)+…+1 (assuming that \t\n\t0 is the coordinate of the shoreline). \n\nOnce, while walking along the embankment of Vladivostok in the evening, Vika saw a group of guys skipping stones across the sea, launching them from the same point with different forces. \n\nShe became interested in what is the maximum number of guys who can launch a stone with their force \t\n\tf i\t\n , so that all \t\n\tf i\t\n are different positive integers, and all \t\n\tn stones touched the water at the point with the coordinate \t\n\tx (assuming that \t\n\t0 is the coordinate of the shoreline). \n\nAfter thinking a little, Vika answered her question. After that, she began to analyze how the answer to her question would change if she multiplied the coordinate \t\n\tx by some positive integers \t\n\t1x 1\t\n , \t\n\t2x 2\t\n , ... , \t\n\tq x q\t\n , which she picked for analysis. \n\nVika finds it difficult to cope with such analysis on her own, so she turned to you for help. \n\nFormally, Vika is interested in the answer to her question for the coordinates \t\n\t1=x⋅x 1\t\n , \t\n\t2=X 1\t\n ⋅x 2\t\n , ... , \t\n\tq=X q−1\t\n ⋅x q\t\n . Since the answer for such coordinates can be quite large, find it modulo \t\n\tM . It is guaranteed that \t\n\tM is prime. \n\n输入格式 \nThe first line of the input contains three integers \t\n\tx ( 1≤x≤10 9 1≤x≤10 9 ), \t\n\tq ( 1≤q≤10 5 1≤q≤10 5 ) and \t\n\tM ( 100≤M≤2⋅10 9 100≤M≤2⋅10 9 ) — the initial coordinate for which Vika answered the question on her own, the number of integers \t\n\tx i\t\n by which Vika will multiply the initial coordinate and prime module \t\n\tM . \n\nThe second line of the input contains \t\n\tq integers \t\n\t1,2,3,…,qx 1\t\n ,x 2\t\n ,x 3\t\n ,…,x q\t\n ( 1≤x i≤10 6 1≤x i≤10 6 ) — the integers described in the statement. \nc++ 实现内容：Here is a possible C++ implementation for the given problem: \n\ncpp \n#include <iostream> \n#include <vector> \n#include <algorithm> \n\nusing namespace std; \n\nlong long powerMod(long long base, long long exp, long long mod) { \n long long result = 1; \n while (exp > 0) { \n if (exp % 2 == 1) { \n result = (result * base) % mod; \n } \n base = (base * base) % mod; \n exp /= 2; \n } \n return result; \n} \n\nint main() { \n long long x, q, M; \n cin >> x >> q >> M; \n\n vector<long long> factors(q); \n for (int i = 0; i < q; i++) { \n cin >> factors[i]; \n } \n\n sort(factors.begin(), factors.end()); \n\n long long result = 1; \n for (int i = 0; i < q; i++) { \n result = (result * powerMod(factors[i], x, M)) % M; \n x = factors[i] * x % M; \n } \n\n cout << result << endl; \n\n return 0; \n} \n \n\nExplanation: \n1. Read the inputs for x, q, and M. \n2. Read the q factors and store them in a vector. \n3. Sort the factors in increasing order. \n4. Iterate over the factors and for each factor, calculate its power modulo M using the powerMod function and multiply it with the current result modulo M. \n5. Update the value of x by multiplying it with the current factor modulo M. \n6. After the loop, output the final result modulo M.