题意:(f(x) = ext{abs}( ext{sin}(frac{p}{q} pi x))),给定(a,b,p,q),求(xin[a,b])最大的(f(x))。
题解:div2都这么仙了吗。。。
根据高中数学知识可以推出要求的就是使得(frac{px mod q}{q})最接近(frac12)的(x),也就是(px mod q)最接近(frac q2)。
有一个结论:([px mod q in [l,r]] = lfloorfrac{px-l}{q} floor - lfloorfrac{px-r-1}{q} floor)。考虑二分(px mod q)与(frac q2)的距离,对于一个(mid),相当于要求是否存在(x)使得(px mod q in [l=frac q2-mid,r=frac q2+mid])。根据上述结论,这等价于(sum_{x=a}^blfloorfrac{px-l}{q} floor - lfloorfrac{px-r-1}{q} floor)是否(>0)。这个式子是可以类欧求的。
求出最小距离以后,用( ext{exgcd})还原(x)即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll Inf = 1e18;
int gi() {
int x = 0, o = 1;
char ch = getchar();
while((ch < '0' || ch > '9') && ch != '-') {
ch = getchar();
}
if(ch == '-') {
o = -1, ch = getchar();
}
while(ch >= '0' && ch <= '9') {
x = x * 10 + ch - '0', ch = getchar();
}
return x * o;
}
ll solve(ll n, ll a, ll b, ll c) {
if(n < 0) {
return 0;
}
if(!n) {
return b / c;
}
if(a >= c || b >= c) {
return solve(n, a % c, b % c, c) + n * (n + 1) / 2 * (a / c) + (n + 1) * (b / c);
}
ll m = (a * n + b) / c;
return m * n - solve(m - 1, c, c - b - 1, a);
}
ll solve(ll l, ll r, ll a, ll b, ll c) {
return solve(r, a, b, c) - solve(l - 1, a, b, c);
}
void exgcd(ll a, ll b, ll &x, ll &y) {
if(!b) {
x = 1, y = 0;
return;
}
exgcd(b, a % b, y, x), y -= a / b * x;
}
ll a, b, p, q;
ll solve(ll p, ll q, ll t) {
ll gg = __gcd(p, q);
if(t % gg != 0) {
return Inf;
}
p /= gg, q /= gg, t /= gg;
ll x, y;
exgcd(p, q, x, y);
x *= t, y *= t;
ll k = (a - x) / q;
x += k * q;
while(x >= a) {
x -= q;
}
while(x < a) {
x += q;
}
return x;
}
int main() {
#ifndef ONLINE_JUDGE
freopen("a.in", "r", stdin);
freopen("a.out", "w", stdout);
#endif
int T = gi();
while(T--) {
a = gi(), b = gi(), p = gi() << 1, q = gi() << 1;
ll l = 0, w = q / 2, r = w;
while(l < r) {
ll mid = (l + r) >> 1;
ll L = w - mid, R = w + mid;
if(solve(a, b, p, q - L, q) - solve(a, b, p, q - R - 1, q)) {
r = mid;
} else {
l = mid + 1;
}
}
cout << min(solve(p, q, w - l), solve(p, q, w + l)) << endl;
}
return 0;
}