HDU 5768 (中国剩余定理 容斥)

2019-04-14 17:17发布

站内文章 / 模拟电子
16551 0 1556

题目链接：点击这里

题意：求区间中7的倍数并且模pi不等于ai的个数. 相当于求模7等于0的数中扣掉模pi等于ai的个数，这个东西看着就很容斥。先枚举限制条件的组合，然后加上模7等于0这个条件，这一堆条件看着就很中国剩余定理，然后搞出一个前缀区间有多少个符合条件的数，加加减减就行了。(嘴炮5分钟，代码两小时=。=) trick：中国剩余定理里面会爆longlong，所以换成快速乘法取模。 #include #include #include #include #include using namespace std; #define maxn 33 long long a[maxn], b[maxn]; int n; long long aa[maxn], bb[maxn]; void gcd (long long a, long long b, long long &d, long long &x, long long &y) { if (!b) { d = a; x = 1; y = 0; } else { gcd (b, a%b, d, y, x); y -= x*(a/b); } } long long mul (long long a, long long b, long long mod) { if (b == 0) return 0; long long ans = mul (a, b>>1, mod); ans = ans*2%mod; if (b&1) ans += a, ans %= mod; return ans; } long long china (int n, long long *a, long long *m, long long R) { long long M = 1, d, y, x = 0; for (int i = 0; i < n; i++) M *= m[i]; for (int i = 0; i< n; i++) { long long w = M/m[i]; gcd (m[i], w, d, d, y); x = (x+ mul (mul (y, w, M), a[i], M)) % M; } long long Min = (x+M)%M; if (Min && R%M >= Min) { return (R/M)+1; } return R/M; } long long go (int num, int &num_of_1, long long R) { num_of_1 = 0; int cnt = 0; for (int bit = 0; bit < n; bit++) if (num&(1<7, bb[cnt++] = 0; return china (cnt, bb, aa, R); } long long solve (long long x) { long long ans = 0; int num_of_1; for (int i = 1; i < (1<long long tmp = go (i, num_of_1, x); if (num_of_1&1) ans += tmp; else ans -= tmp; } return ans; } int main () { int t, kase = 0; scanf ("%d", &t); while (t--) { long long x, y; scanf ("%d%lld%lld", &n, &x, &y); for (int i = 0; i < n; i++) { scanf ("%lld%lld", &a[i], &b[i]); } printf ("Case #%d: %lld ", ++kase, (y/7 - (x-1)/7) - (solve (y)-solve (x-1))); } return 0; }

热门文章