HDU 5768 中国剩余定理

题目链接:Lucky7

题意:求在l和r范围内,满足能被7整除,而且不满足任意一组,x mod p[i] = a[i]的数的个数。

思路:容斥定理+中国剩余定理+快速乘法。 (奇+ 偶-)

#include <stdio.h>
#include <string.h>
#include <iostream>
using namespace std; #define LL long long
#define FOR(i, n) for (int i=0; i<n; ++i)
LL l, r; int extend_gcd(LL a, LL b, LL &x, LL &y) {
if (b == 0) {
x = 1;
y = 0;
return a;
} else {
int r = extend_gcd(b, a%b, y, x);
y -= x*(a/b);
return r;
}
} LL qMul(LL a, LL b, LL mod) {
a %= mod;
LL ret = 0;
while(b) {
if (b & 1) ret = (ret + a) % mod;
b >>= 1;
a = (a + a) % mod;
}
return ret;
} LL CRT(LL *a, LL *m, int n) {
LL M = 1;
for (int i=0; i<n; ++i) M *= m[i]; LL x = 0;
LL d, y;
for (int i=0; i<n; ++i) {
//LL d, y;
LL tm = M/m[i];
extend_gcd(m[i], tm, d, y);
x = (x + qMul( qMul(d, tm, M), a[i], M)) % M; // 参数传递有顺序
}
x = (x + M) % M;
return (r+M-x)/M - (l-1+M-x)/M; // 直接返回l r区间有多少个解。
} LL a[20], m[20];
LL chu[20], rema[20]; int main() {
freopen("1.in.cpp", "r", stdin);
int t;
scanf("%d", &t);
int cas = 0; while(t--) {
int n;
scanf("%d%lld%lld", &n, &l, &r);
FOR(i, n) {
scanf("%lld%lld", &chu[i], &rema[i]);
}
LL tot = (1<<n);
LL ans = r/7 - (l-1)/7; for (int i=1; i<tot; ++i) {
//cout << i << "++++\n";
int cnt = 0;
FOR (j, n) {
if (i&(1<<j)) {
m[cnt] = chu[j];
a[cnt] = rema[j];
cnt++;
}
}
m[cnt] = 7, a[cnt] = 0;
cnt++;
LL tans = CRT(a, m, cnt);
cnt = (cnt&1) ? 1 : -1;
ans += tans * cnt;
}
//cout << "++++\n";
printf("Case #%d: %I64d\n", ++cas, ans);
}
return 0;
}
上一篇:LwIP移植和使用


下一篇:[阿里DIN] 深度兴趣网络源码分析 之 整体代码结构