CF1182F Maximum Sine

Title Link: Luo Gu

Title Description: find the integer $x\in [a,b] $to make $| $2px \ mod \ 2q-q| $minimum. If there are multiple $x $output minimum.

Data range: $1\leq a,b,p,q\leq 10^9$

The first question is not a template.

First of all, try dichotomy. How to judge $2px \ mod \ 2q \in [l,r] $? We found

$$[2px \ mod \ 2q \in [l,r]]=\lfloor\frac{2px-l}{2q}\rfloor-\lfloor\frac{2px-r-1}{2q}\rfloor$$

So there is $x\in [a,b] $to make $2px \ mod \ 2q \in [l,r] $. It is only necessary to judge whether $\ sum {x = a} ^ B (\ lfloor \ frac {2px-l} {2q} \ rfloor - \ lfloor \ frac {2px-r-1} {2q} \ rfloor) $is greater than 0. This is done by eurolike calculation.

After finding the minimum deviation value of $l $, we can use the extended Europe to solve the congruence equation. Time complexity $O(\log^2 n) $.

 1 #include<bits/stdc++.h>
 2 #define Rint register int
 3 using namespace std;
 4 typedef long long LL;
 5 LL t, a, b, p, q, len;
 6 inline LL calc(LL a, LL b, LL c, LL n){
 7     if(!a || !n) return (n + 1) * (b / c);
 8     if(n < 0) return 0;
 9     LL m = (a * n + b) / c;
10     if(a >= c || b >= c) return calc(a % c, b % c, c, n) + (n * (n + 1) >> 1) * (a / c) + (n + 1) * (b / c);
11     return m * n - calc(c, c - b - 1, a, m - 1);
12 }
13 inline LL exgcd(LL a, LL b, LL &x, LL &y){
14     if(!b){x = 1; y = 0; return a;}
15     LL gcd = exgcd(b, a % b, y, x);
16     y -= a / b * x;
17     return gcd;
18 }
19 int main(){
20     scanf("%lld", &t);
21     while(t --){
22         scanf("%lld%lld%lld%lld", &a, &b, &p, &q);
23         LL l = 0, r = q, mid, P = p << 1, Q = q << 1;
24         while(l < r){
25             mid = l + r >> 1;
26             LL L = q - mid, R = q + mid + 1;
27             if(calc(P, Q - L, Q, b) + calc(P, Q - R, Q, a - 1) - calc(P, Q - L, Q, a - 1) - calc(P, Q - R, Q, b) > 0) r = mid;
28             else l = mid + 1;
29         }
30         LL x, y, gcd = exgcd(P, Q, x, y), ans = 1e9; P /= gcd; Q /= gcd;
31         if((q - l) % gcd == 0){
32             LL xx = (q - l) / gcd * x; xx += (a - xx) / Q * Q;
33             while(xx >= a) xx -= Q; while(xx < a) xx += Q;
34             ans = min(ans, xx);
35         }
36         if((q + l) % gcd == 0){
37             LL xx = (q + l) / gcd * x; xx += (a - xx) / Q * Q;
38             while(xx >= a) xx -= Q; while(xx < a) xx += Q;
39             ans = min(ans, xx);
40         }
41         printf("%lld\n", ans);
42     }
43 }
CF1182F

Later, I saw a wave of official solutions, and found that it was a block like BSGS, with a time complexity of $O(\sqrt{n}) $. (if you write badly, you need to bring a log...)

(the above method is better)

(the most important thing is to look a little bigger...)

Tags: PHP

Posted on Fri, 01 Nov 2019 09:17:11 -0700 by Yuzi