Data Processing

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)

Problem Description

Chinachen is a football fanatic, and his favorite football club is Juventus fc. In order to buy a ticket of Juv, he finds a part-time job in Professor Qu’s lab.
And now, Chinachen have received an arduous task——Data Processing.
The data was made up with N positive integer (n1, n2, n3, … ), he may calculate the number , you can assume mod N =0. Because the number is too big to count, so P mod 1000003 is instead.
Chinachen is puzzled about it, and can’t find a good method to finish the mission, so he asked you to help him.

Input

The first line of input is a T, indicating the test cases number.
There are two lines in each case. The first line of the case is an integer N, and N<=40000. The next line include N integer numbers n1,n2,n3… (ni<=N).

Output

For each test case, print a line containing the test case number ( beginning with 1) followed by the P mod 1000003.

Sample Input

2
3
1 1 3
4
1 2 1 4

Sample Output

Case 1:4
Case 2:6
Hint
Hint: You may use “scanf” to input the data.

题意：

就是按照图中的式子求出P的值并取模。

思路：

因为求的是除法的取模，所以要求出除数的逆元。因为在数学是不满足(a % mod) / (b % mod) = (a / b) % mod的，所以就要就要变成乘法的形式，所以就变成a % mod * （b的逆元）% mod，在求逆元的时候就是用费马小定理以及快速幂。

#include <iostream>
#include <cstdio>
using namespace std;
typedef long long ll;
const int mod = 1000003;
ll QuickPow(ll a, ll b) {
    ll ans = 1;
    while (b) {
        if (b & 1) ans = ans * a % mod;
        a = a * a % mod;
        b >>= 1;
    }
    return ans;
}
int main() {
    int t;
    scanf("%d", &t);
    for (int Case = 1; Case <= t; Case++) {
        ll n, k, sum = 0;
        scanf("%lld", &n);
        for (int i = 0; i < n; i++) {
            scanf("%lld", &k);
            sum = sum + QuickPow(2, k) % mod;
        }
        n = QuickPow(n, mod - 2);
        printf("Case %d:%lld\n", Case, sum * n % mod);
    }
    return 0;
}