2016 Multi-University Training Contest 4

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=5768

题目大意：给你区间[L,R]，问你[L, R]中有多少个数字x满足x%7=0且x%p[i]≠a[i];

数据范围：1≤L<R≤10^18，0<a[i]<p[i]≤10^5，p[i],a[i]有n对，0≤n≤15；

解题思路：这道题赛场上想到了正解，但是因为一些细节处理上经验不足导致WA到结束（对拍都能过，大数处理的问题）

首先看到所求的条件像是求几个集合的并，而n范围恰好合乎容斥范围，对n个条件做容斥，其中处理交集的时候，即求同时满足几个条件的x时显然需要用中国剩余定理来计算。中国剩余定理求得一个合法解ret之后，所有解就是ret+k*M，M就是当前集合那些p[i]的乘积。这里写个函数算一下[L,R]之间%M=ret的有多少个就好了。

而对于特殊条件%7=0，起初想把该条件变为6个条件%7=1,%7=2...%7=6，这样加上给的n个条件一共21个，复杂度2^21*21加上乱七八糟常数，还有T组数据肯定会TLE，于是考虑直接当成条件%7≠0处理。在求其他条件与这个特殊条件的交的时候就用其他条件的交-其他条件与“%7=0”的交计算即可，这样O（2^16*16）很容易接受。

大概思路就是这样，其中需要注意的点：

1、最好写一个Get(L, R, P, X)函数表示[L,R]区间中有多少个数%P=X，这个函数要写稳。

2、由于这类问题数据范围十分的大，CRT中有一句话ret=(ret+tm*x*a[i])%M是需要写快速乘计算，不然会爆long long，惨死…

3、写快速乘的时候一定要记得幂的位置不能是负数！

  1 #include <cstdio>
  2 #include <cstdlib>
  3 #include <cmath>
  4 #include <cstring>
  5 #include <algorithm>
  6 using namespace std;
  7 typedef long long LL;
  8 
  9 const int MaxN = 30;
 10 int T, n, cas;
 11 LL ans, L, R;
 12 LL P[MaxN + 5], A[MaxN + 5];
 13 
 14 void Init()
 15 {
 16     scanf("%d%lld%lld", &n, &L, &R);
 17     for (int i = 1; i <= n; i++) scanf("%lld%lld", &P[i], &A[i]);
 18 }
 19 
 20 LL Get(LL L, LL R, LL p, LL x)
 21 {
 22     LL lm = L % p;
 23     LL lc = L / p;
 24     LL rm = R % p;
 25     LL rc = R / p;
 26     LL ans = rc - lc;
 27     if (lm > x) ans--;
 28     if (rm >= x) ans++;
 29     return ans;
 30 }
 31 
 32 LL extend_gcd(LL a, LL b, LL &x, LL &y)
 33 {
 34     if (b == 0) {
 35         x = 1; y = 0;
 36         return a;
 37     }else {
 38         LL r = extend_gcd(b, a % b, y, x);
 39         y -= x * (a / b);
 40         return r;
 41     }
 42 }
 43 
 44 LL qwr(LL x, LL y, LL MOD)
 45 {
 46     x = x % MOD;
 47     LL ans = 0;
 48     while (y != 0) {
 49         if (y & 1) ans = (ans + x) % MOD;
 50         y = y / 2LL;
 51         x = (x + x) % MOD;
 52     }
 53     return ans;
 54 }
 55 
 56 LL CRT(LL a[], LL m[], int n)
 57 {
 58     LL M = 1;
 59     for (int i = 1; i <= n; i++) M *= m[i];
 60     LL ret = 0;
 61     for (int i = 1; i <= n; i++) {
 62         LL x, y;
 63         LL tm = M / m[i];
 64         extend_gcd(tm, m[i], x, y);
 65         ret = (ret + qwr(qwr(x, tm, M), a[i], M)) % M;
 66     }
 67     return (ret + M) % M;
 68 }
 69 
 70 void Solve()
 71 {
 72     ans = 0;
 73     for (int s = 1; s <= ((1 << (n + 1)) - 1); s++) {
 74         LL p[MaxN + 5], a[MaxN + 5];
 75         if (s == 1) ans += (R - L + 1) - Get(L, R, 7, 0);
 76         else {
 77             int tot = 0; LL Fac = 1;
 78             for (int i = 1; i <= n; i++) 
 79                 if (s & (1 << i)) p[++tot] = P[i], a[tot] = A[i], Fac *= p[tot];
 80             if (s & 1) {
 81                 LL t = ((tot + 1) & 1) ? 1 : -1;
 82                 LL crt1 = CRT(a, p, tot);
 83                 a[++tot] = 0; p[tot] = 7;
 84                 LL crt2 = CRT(a, p, tot);
 85                 ans += t * (Get(L, R, Fac, crt1) - Get(L, R, Fac * (LL)7, crt2));
 86             }
 87             else {
 88                 LL t = (tot & 1) ? 1 : -1;
 89                 LL crt = CRT(a, p, tot);
 90                 ans += t * Get(L, R, Fac, crt);
 91             }
 92         }
 93     }
 94     printf("Case #%d: %lld\n", ++cas, R - L + 1 - ans);
 95 }
 96 
 97 int main()
 98 {
 99     scanf("%d", &T);
100     for (int i = 1; i <= T; i++) {
101         Init();
102         Solve();
103     }
104 }

View Code

2016 Multi-University Training Contest 4 - 1005 (hdu5768)

推荐阅读