本文主要是介绍hdu - 3049 - Data Processing（乘法逆元），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！
题意：N（N<=40000）个数n1, n2, ..., nN (ni<=N)，求(2 ^ n1 + 2 ^ n2 + ... + 2 ^nN) / N % 1000003。
题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=3049
——>>RJ白书上说“由于‘乘法逆’太重要了……”，上一年南京区赛同学也碰到了求逆元……现在，学习了。。
什么是乘法逆？ab % m = 1 （这里的 a, b 分别都是模 m 的同余等价类），a 模 m 的乘法逆是 b，同时，b 模 m 的乘法逆是a。
乘法逆有什么用？这个用处可还真不小。。如果要求 a / b % m（保证 b | a），但是 a 很大很大，比如 a = 2 ^ 40000，这个式子可不等价于 (a % m) / (b % m) % m。。这时，乘法逆就可以上场了。。一个数除以 b 后模 m，等价于该数乘以 b 模 m 的乘法逆后模 m。。于是上式可变成 a * b的乘法逆 % m，这就容易多了，就是 (a % m) * (b的乘法逆 % m) % m。。
怎么求乘法逆？要求 a 模 m 的乘法逆，设其为 x，因为 a * x % m = 1，所以 a * x + m * y = 1。。这是什么，一元二次方程，于是乎，扩展欧几里得飞一下就出来了。。
#include <cstdio>typedef long long LL;const int MOD = 1000003;
const int MAXN = 40000 + 10;int N, kase;
LL sum;
int pow2[MAXN];void GetPow2()
{pow2[0] = 1;for (int i = 1; i < MAXN; ++i){pow2[i] = (pow2[i - 1] << 1) % MOD;}
}void Read()
{int n;sum = 0;scanf("%d", &N);for (int i = 0; i < N; ++i){scanf("%d", &n);sum = (sum + pow2[n]) % MOD;}
}void gcd(LL a, LL b, LL& d, LL& x, LL& y)
{if (!b){d = a;x = 1;y = 0;return;}else{gcd(b, a % b, d, y, x);y -= a / b * x;}
}LL Inv(int a, int n)
{LL ret, d, y;gcd(a, n, d, ret, y);return d == 1 ? (ret + n) % n : -1;
}void Solve()
{LL ret;LL inv = Inv(N, MOD);ret = sum * inv % MOD;printf("Case %d:%I64d\n", ++kase, ret);
}int main()
{int T;kase = 0;GetPow2();scanf("%d", &T);while (T--){Read();Solve();}return 0;
}
这篇关于hdu - 3049 - Data Processing（乘法逆元）的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！
