题意
求 $[a, b]$ 中使得 $f(x) = \left|\sin\left(\frac{p}{q}\pi x\right)\right|$ 取得最大值的整数 $x$。且 $x$ 可能有多个取值，请输出符合条件的最小的 $x$。
$t$ 组询问，每次给出 $a,b,p,q$。
数据范围满足 $1 \le t \le 100,0 \le a \le b \le 10^9,1 \le p,q \le 10^9$
单独为本题开一篇文章，理由在于其具有复杂度优秀的三种解法，复杂度逐渐变低而效率逐渐提高。
扩展做法将专注于解决从本题中抽象出的模型。
于是先放一个最好理解的本题做法，作为讲本题时的内容
题解
观察容易得出要求一个小于线性的做法。
考虑如何转化本题的设问。
要求使 $f(x) =\left|\sin\left(\frac{p}{q}\pi x\right)\right|$ 最大的整数 $x$，考虑三角函数的周期性，我们有如下转化。
要求上式 $\sin$ 的绝对值最大，即要求 $\sin$ 括号内的值 $\frac{p}{q}\pi x $ 最接近于 $(k + \frac{1}{2}) \pi ,k \in Z$。
于是就是 $\frac{px}{q}$ 最接近于 $k + \frac12$
也就是 $\frac{px}{q}$ 的小数部分最接近于 $\frac12$
发现带着小数不舒服，考虑变成整数操作，发现可以直接同乘 $2q$
就变成了 $2px \bmod 2q$ 最接近于 $q$（这个取模可以参考模运算下的乘法，把取小数看成对 $1$ 取模来理解）。
于是这题最难的转化就结束了。
剩下的部分类似于 BSGS 的过程，具体而言，把 $[l,r]$ （即题中的 $[a,b]$）分成长度为根号级别的根号块，首先处理出每个块块首的元素的 $2px \bmod 2q$ 的值，记录并排序。
然后的操作就是每次将每个块内向后移动一个位置，即变成 $2p(x+1) \bmod 2q$。
于是每次操作相当于把我们排序后的数组都加上 $2p$ 这个定值，显然对于每个数都加上再找到最接近 $q$ 的值有很多冗余操作，因为很多位置不可能对答案产生贡献。
考虑如何减少冗余操作，我们发现每次操作是整体加上 $2p$ 再对 $2q$ 取模，相当于把最后几项旋转到最前边。
而这样做代码实现不很好写，考虑加上这些 $2p$ 之后取模要找与 $q$ 最接近的数，我们可以直接把 $q$ 减去这些 $2p$ 然后取模，在原数列中二分找到可能产生贡献的那个位置，把前后两个位置都考虑下取个 $\min$ 即可。
有一些边界需要注意，这样的做法是 $O(\sqrt{n} \log n)$ 的，因为分块后有 $\sqrt{n}$ 次移动且每次二分的复杂度是 $\log n$。
作为对不易描述的细节的说明，放一下代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
| #include<cstdio>
#include<cmath>
#include<algorithm>
namespace Pozhu{
using namespace std;
typedef long long ll;
#define N 100010
ll l,r,p,q;
struct node{
ll v,id;
node(ll _v = 0,ll _id = 0) : v(_v),id(_id){}
friend bool operator < (node a,node b)
{return a.v != b.v ? a.v < b.v : a.id < b.id;}
friend bool operator == (node a,node b)
{return a.v == b.v;}
}a[N];
void main()
{
scanf("%lld%lld%lld%lld",&l,&r,&p,&q);
int siz = sqrt(r - l + 1);
int tot = 0;
ll mod = q + q;
ll maxx = 0x3f3f3f3f3f3f3f3f,mxpos;
for(ll i = l;i <= r;i += siz)
{
if(i + siz - 1 <= r) a[++tot] = node(2 * p * i % mod,i);
else
{
for(int j = i;j <= r;j++)
{
ll val = abs(2 * p * j % mod - q);
if(val < maxx)
maxx = val,mxpos = j;
}
}
}
sort(a+1,a+tot+1);
tot = unique(a+1,a+tot+1)-a-1;
for(ll i = 0,tmp = 0;i < siz;i++,tmp = (tmp + 2 * p) % mod)
{
ll nval = (q - tmp + mod) % mod;
int pos = lower_bound(a+1,a+tot+1,node(nval,-1)) - a;
if(pos <= tot)
{
if((a[pos].v - nval) % mod < maxx || ((a[pos].v - nval) % mod == maxx && a[pos].id + i < mxpos))
maxx = (a[pos].v - nval) % mod,mxpos = a[pos].id + i;
}
else
{
if((mod - (nval - a[1].v)) % mod < maxx || ((mod - (nval - a[1].v)) % mod == maxx && a[1].id + i < mxpos))
maxx = (mod - (nval - a[1].v)) % mod,mxpos = a[1].id + i;
}
pos--;
if(pos >= 1)
{
if((nval - a[pos].v) % mod < maxx || ((nval - a[pos].v) % mod == maxx && a[pos].id + i < mxpos))
maxx = (nval - a[pos].v) % mod,mxpos = a[pos].id + i;
}
else
{
if((mod - (a[tot].v - nval)) % mod < maxx || ((mod - (a[tot].v - nval)) % mod == maxx && a[tot].id + i < mxpos))
maxx = (mod - (a[tot].v - nval)) % mod,mxpos = a[tot].id + i;
}
}
printf("%lld\n",mxpos);
return;
}
}
signed main()
{
int T;
for(scanf("%d",&T);T;T--)
Pozhu :: main();
return 0;
}
|
于是原题题解的部分结束了。
下面的内容（如果我写了的话）将作为对于这题的延申。
扩展
我们从上边那题中抽象出的问题为：
求这个式子的最大值。
