啊我死了。
肝了三天的毒瘤题......他们考场怎么A的啊。
大意：
给你若干个形如 
的方程组，求最小整数解。
嗯......exCRT的变式。
考虑把前面的系数化掉：
然后就是exCRT板子了。
我TM想要自己写出一个板子，然后GG了......
我快疯了。
然后抄了板子(滑稽)
注意细节，快速幂/乘的时候，b位置不要传负数。
1 #include2 #include 3 #include 4 5 typedef long long LL; 6 const int N = 100010; 7 8 std::multiset S; 9 std::multiset ::iterator it; 10 int n, m, Time, vis[N]; 11 LL a[N], p[N], awd[N], use[N]; 12 13 LL Val; 14 LL gcd(LL a, LL b) { 15 if(!b) { 16 return a; 17 } 18 return gcd(b, a % b); 19 } 20 inline LL lcm(LL a, LL b) { 21 return a / gcd(a, b) * b; 22 } 23 void exgcd(LL a, LL b, LL &x, LL &y) { 24 if(!b) { 25 x = Val / a; 26 y = 0; 27 return; 28 } 29 exgcd(b, a % b, x, y); 30 std::swap(x, y); 31 y -= (a / b) * x; 32 return; 33 } 34 inline LL mod(LL a, LL c) { 35 while(a >= c) { 36 a -= c; 37 } 38 while(a < 0) { 39 a += c; 40 } 41 return a; 42 } 43 inline LL mul(LL a, LL b, LL c) { 44 LL ans = 0; 45 a %= c; 46 b %= c; 47 while(b) { 48 if(b & 1) { 49 ans = mod(ans + a, c); 50 } 51 a = mod(a << 1, c); 52 b = b >> 1; 53 } 54 return ans; 55 } 56 inline LL qpow(LL a, LL b, LL c) { 57 LL ans = 1; 58 a %= c; 59 while(b) { 60 if(b & 1) { 61 ans = mul(ans, a, c); 62 } 63 a = mul(a, a, c); 64 b = b >> 1; 65 } 66 return ans; 67 } 68 inline LL abs(LL a) { 69 return a < 0 ? -a : a; 70 } 71 inline LL inv(LL a, LL c) { 72 LL x, y; 73 Val = 1; 74 exgcd(a, c, x, y); 75 return mod(x, c); 76 } 77 //----math---- 78 79 inline void solve_p1() { 80 LL ans = 0; 81 for(int i = 1; i <= n; i++) { 82 LL temp = (a[i] - 1) / use[i] + 1; 83 ans = std::max(ans, temp); 84 } 85 printf("%lld\n", ans); 86 return; 87 } 88 89 inline void solve_n1() { 90 LL g = gcd(use[1], p[1]); 91 if(a[1] % g) { 92 puts("-1"); 93 return; 94 } 95 LL x, y; 96 Val = a[1]; 97 exgcd(use[1], p[1], x, y); 98 // use[1] * x + p[1] * y == a[1] 99 LL gap = (use[1] / g);100 //printf("gap = %lld y = %lld \n", gap, y);101 LL yy = (y % gap - gap) % gap;102 //printf("yy = %lld \n", yy);103 LL dt = (y - yy) / gap;104 //printf("dt = %lld \n", dt);105 x += dt * (p[1] / g);106 //printf("x = %lld \n", x);107 printf("%lld\n", x);108 return;109 }110 111 inline void solve_a() {112 LL large = 0;113 for(int i = 1; i <= n; i++) {114 large = std::max(large, (a[i] - 1) / use[i] + 1);115 LL g = gcd(use[i], p[i]);116 if(a[i] % g) {117 puts("-1");118 return;119 }120 if(p[i] == 1) {121 vis[i] = Time;122 continue;123 }124 //printf("%lld %lld %lld \n", use[i], p[i], a[i]);125 a[i] /= g;126 p[i] /= g;127 use[i] /= g;128 use[i] %= p[i];129 a[i] %= p[i];130 if(!use[i]) {131 if(!a[i]) {132 vis[i] = Time;133 continue;134 }135 else {136 puts("-1");137 //printf("%lld %lld %lld \n", use[i], p[i], a[i]);138 return;139 }140 }141 LL Inv, temp;142 Val = 1;143 exgcd(use[i], p[i], Inv, temp);144 Inv = mod(Inv, p[i]);145 //printf("Inv = %lld \n", Inv);146 a[i] = mul(Inv, a[i], p[i]);147 }148 // x = a[i] (mod p[i])149 150 /*for(int i = 1; i <= n; i++) {151 printf("x === %lld mod %lld \n", a[i], p[i]);152 }*/153 154 bool fd = 0;155 LL A = 0, P = 1;156 for(int i = 1; i <= n; i++) {157 //printf("%d \n", i);158 if(vis[i] == Time) {159 continue;160 }161 if(!fd) {162 A = a[i];163 P = p[i];164 fd = 1;165 continue;166 }167 // merge i168 LL x, y;169 LL C = ((a[i] - A) % p[i] + p[i]) % p[i];170 LL g = gcd(P, p[i]);171 if(C % g) {172 puts("-1");173 return;174 }175 Val = g;176 exgcd(P, p[i], x, y);177 x = mul(x, C / g, P / g * p[i]);178 A += mul(x, P, P / g * p[i]);179 P *= p[i] / g;180 A = (A + P) % P;181 }182 // x = A (mod P)183 // 1 * x + y * P = A184 185 LL x, y;186 Val = A;187 exgcd(1, P, x, y);188 x = mod(x, P);189 if(x < large) {190 x += P * ((large - x - 1) / P + 1);191 }192 printf("%lld\n", x);193 return;194 }195 196 inline void solve() {197 scanf("%d%d", &n, &m);198 for(int i = 1; i <= n; i++) {199 scanf("%lld", &a[i]);200 }201 for(int i = 1; i <= n; i++) {202 scanf("%lld", &p[i]);203 }204 for(int i = 1; i <= n; i++) {205 scanf("%lld", &awd[i]);206 }207 for(int i = 1; i <= m; i++) {208 LL x;209 scanf("%lld", &x);210 S.insert(x);211 }212 for(int i = 1; i <= n; i++) {213 it = S.upper_bound(a[i]);214 if(it != S.begin()) {215 it--;216 }217 use[i] = (*it);218 S.erase(it);219 S.insert(awd[i]);220 }221 222 //-------------------- p = 1 30pts -------223 bool f = 1;224 for(int i = 1; i <= n; i++) {225 if(p[i] > 1) {226 f = 0;227 break;228 }229 }230 if(f) {231 solve_p1();232 return;233 }234 235 //-------------------- n = 1 30pts -------236 if(n == 1) {237 solve_n1();238 return;239 }240 241 solve_a();242 return;243 }244 245 int main() {246 247 int T;248 scanf("%d", &T);249 for(Time = 1; Time <= T; Time++) {250 solve();251 if(Time < T) {252 S.clear();253 }254 }255 256 return 0;257 }
一共提交了14次.......