HDU 3049 Data Processing(a/b mod c, 逆元)

本文主要是介绍HDU 3049 Data Processing(a/b mod c, 逆元)，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目：LINK

题目求 P = (2^(n1) + 2^(n2) + ...+ 2^(nk))/n  (mod n)
    对于分子部分我们可以打表求得(ps:用快速幂多次计算会TLE), 问题成了a/n mod n, 我们可以用下面解法求得。
1)， a/b mod c ==>  (a mod bc) / b 对于所有的情况都适用，要注意的问题就是 (b*c)*(b*c) 会不会溢出,这儿的数据范围不会溢出.
2), 求利用逆元求解。逆元存在的条件是gcd(b, c) == 1
    1‘ 如果c 是质数,可以利用费马小定理求得，b ^(-1) = b^(c-2) .
    2’ 一般情况下可以利用扩展欧几里得求得， 设b的逆元是x , bx= 1 mod c, ==>  bx + cy = 1 求解(x, y) 中x就是逆元，(gcd(b, c) != 1)  没有逆元)

1)code: 

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef __int64 LL;
#define MOD 1000003
#define N 41111
LL n, num[N], b[N];
LL sol()
{LL ret = 0, mod = MOD*n;b[0] = 1;for(int i = 1; i<=40001; i++) {b[i] = 2*b[i-1];if(b[i]>= mod) b[i] -= mod;}for(int i = 1; i<= n; i++) {LL tmp = b[num[i]];ret += tmp; ret %= mod;}return ret / n;
}
int main()
{
#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGEint t, time = 0;scanf("%d", &t);while( t-- ) {scanf("%I64d", &n);for(LL i = 1; i <= n; i++) {scanf("%I64d", &num[i]);}LL ans = sol();printf("Case %d:", ++time);printf("%I64d\n", ans);}return 0;
}

2) 1' code :

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef __int64 LL;
#define MOD 1000003
#define N 41111
LL n, num[N], b[N];LL powmod(LL x, LL y, LL mod)
{LL ret = 1;while(y) {if(y&1) ret = ret * x, ret %= mod;y >>= 1;x *= x;  x %= mod;}return ret;
}
LL sol()
{LL ret = 0;for(int i = 1; i<= n; i++) {LL tmp = b[num[i]];ret += tmp; ret %= MOD;}ret *= powmod(n, MOD-2, MOD); //n^(MOD - 2) 就是逆元ret %= MOD;return ret;
}
int main()
{
#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGEint t, time = 0;scanf("%d", &t);b[0] = 1;for(int i = 1; i<=40001; i++) {b[i] = 2*b[i-1];if(b[i]>= MOD) b[i] -= MOD;}while( t-- ) {scanf("%I64d", &n);for(LL i = 1; i <= n; i++) {scanf("%I64d", &num[i]);}LL ans = sol();printf("Case %d:", ++time);printf("%I64d\n", ans);}return 0;
}

2) 2' code: 

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef __int64 LL;
#define MOD 1000003
#define N 41111
LL n, num[N], b[N];
LL egcd(LL a, LL b, LL &x, LL &y)
{if(!b) {x = 1; y = 0; return a;}LL gcd = egcd(b, a%b, x, y);LL t = x; x = y; y = t - (a / b) * y;return gcd;
}
LL Inval(LL a, LL m)
{LL x, y;egcd(a, m, x, y);return (x%m + m) % m;
}
LL sol()
{LL ret = 0;for(int i = 1; i<= n; i++) {LL tmp = b[num[i]];ret += tmp; ret %= MOD;}ret = ret *Inval(n, MOD);ret %= MOD;return ret;
}
int main()
{
#ifndef ONLINE_JUDGEfreopen("in.txt", "r", stdin);
#endif // ONLINE_JUDGEint t, time = 0;scanf("%d", &t);b[0] = 1;for(int i = 1; i<=40001; i++) {b[i] = 2*b[i-1];if(b[i]>= MOD) b[i] -= MOD;}while( t-- ) {scanf("%I64d", &n);for(LL i = 1; i <= n; i++) {scanf("%I64d", &num[i]);}LL ans = sol();printf("Case %d:", ++time);printf("%I64d\n", ans);}return 0;
}

这篇关于HDU 3049 Data Processing(a/b mod c, 逆元)的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---