Given a sequence of N integers a1, a2, ..., aN, any contiguous segment of elements in the original sequence is called a subarray. Two subarrays are considered different if there exists at least one element that belongs to one subarray but not the other.
For example, in the sequence {a1, a2, a3, a4}, the subarrays are: {a1}, {a2}, {a3}, {a4}, {a1, a2}, {a2, a3}, {a3, a4}, {a1, a2, a3}, {a2, a3, a4}, {a1, a2, a3, a4}.
The task is to count the number of subarrays such that the sum of the M-th powers of the elements in the subarray is divisible by K. first line : N,M,K (1 ≤ N ≤ 10^5; 1 ≤ M ≤10^18,1 ≤ K ≤ 10^5) second line : a1,a2,..an (1 ≤ ai ≤ 10^50)
Auto comment: topic has been updated by conhaicau (previous revision, new revision, compare).
This one is quite tricky. Here is my approach. We can iterate through each subarray using two for loops, and then for each element in a subarray, we can raise it to the $$$M^{th}$$$ power. To do this, let's keep a variable $$$cnt$$$. To make sure we do not exceed any maximum integer limit, we can take the integer $$$\mod k$$$ each time as we are raising it to the $$$M^{th}$$$ power. After raising it to the $$$M^{th}$$$ power, if the $$$\mod k$$$ is $$$0$$$, we increment the count by $$$1$$$. After going through all the elements, if our $$$cnt$$$ is equal to the subarray length, we have found a subarray that satisfies the conditions, and we can increment our total answer by $$$1$$$.
A cool optimization trick is to notice that once $$${a_i}^n \cong 0 \mod k$$$, we can stop iterating there, because it will never be able to not be congruent to $$$0$$$ no matter how much we multiply. Hope this helps!
why cant we just simply find the value of a[i]^m % k individually for each element, then do simple subarray sum % k == 0 iteration using map?
Damn I read the problem incorrectly. I'm not quite sure how to find the sum of mods with powers that big in good time.
I think that you're right about the map trick. And you can probably even use a frequency array since $$$k$$$ is low. Finding those big mods is tricky though.
a ^ b mod m = (a % m) ^ (b % phi(m)) mod m where a and m must be co prime. if a and m are indeed coprime, finding the result is trivial,
If however, a and m are not comprime, even then a ^ b mod m = (a % m) ^ b mod m holds, and finding the result using binexp still fits in time.
$$$\phi$$$ is Euler's totient function, correct? So what you're saying is that $$$a^b \mod m \cong (a \mod m)^{b \mod \phi(m)}$$$ when $$$a$$$ and $$$m$$$ are coprime. If they are not coprime, can you set $$$a_p = \frac{a}{\gcd(a, m)}$$$ and $$$m_p = \frac{m}{\gcd(a, m)}$$$ and apply the rule above to $$$a_p$$$ and $$$m_p$$$ and then multiply by the $$$\gcd(a, m)$$$ after finishing to get the answer?
No the second part of your comment is incorrect and I did not imply that. Example: take a = 6, b = 2, m = 12, real value is 0, but your claim shows 6. I think you are confusing something else. ak = bk mod(m) equals a = b mod(m/gcd(m, k)), basically if you divide both sides by k, you also need to remove the common factor between k and the mod). As you can see this fact has nothing to do with your claim.
a ^ b mod m = (a % m) ^ b mod m should be enough to calculate the desired value easily as binary exp will be in order log2(m) which is perfectly doable for all the numbers. Since the base is also <= k <= 1e6, the multiplications inside bin exp are fast and within int64_max.
Ohh okay I see now. I saw something the other day where they did something like that. Thanks
how to be good at math how do you learn
Too easy to ask someone for help! You need to quit competitive programming right now! (Ps: Go touch grass, weeaboo!)
you can use binary exponentation to set
a[i] = (a[i]^m) mod kinO(log(m)), then use prefix sum and a map to count subarrays divisible byk.