SUPERPW - SuperPower
You are given two arrays a and b of size n. You are also given a number p.
You are supposed to find ( a[0]^b[0] + a[1]^b[1] + ... a[n-1]^b[n-1] ) % p
You must also know that
( a + b ) % c = ( a%c + b%c ) % c
and
( a * b ) % c = ( a%c * b%c ) % c
Warning: The actual value a[i]^b[i] may not fit in any primitive data-type, infact it may not even fit in the RAM.
Input
First line contains T ( T <= 12 ) which is the number of test-cases.
Then contain T-blocks having the following format.
First line of each block contains a number n which is the number of elements of arrays a and b and the number p.
Second line of each block contains n-integers which are the values a[0], a[1] ... a[n-1]
Third line of each block contains n-integers which are the values b[0], b[1] ... b[n-1]
Output
For each block of input print the answer.
Example
Input: 2 3 5 2 3 4 1 1 1 4 4 2 2 2 2 1 1 1 1 Output: 4 0
hide comments
nadstratosfer:
2019-02-14 21:13:44
0 < n, p, a[i], b[i] < 50,000. |
|
John and the cows:
2013-08-15 05:22:14
why is the time limit so ... long ??? |
Added by: | .:: Pratik ::. |
Date: | 2010-04-16 |
Time limit: | 1.417s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: NODEJS OBJC PERL6 SQLITE VB.NET |