题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3025
数据加强版:http://oi.cdshishi.net/contestoi/problem_show.php?pid=1063
数据生成器(要求支持假分数):http://paste.ubuntu.com/23391949/
好久没有做推式子的题目啦!
首先这题可以用Farey sequence直接做:https://en.wikipedia.org/wiki/Farey_sequence
具体实现上可能需要用Stern–Brocot tree:https://en.wikipedia.org/wiki/Stern%E2%80%93Brocot_tree
上述做法把此题变成裸题,然而不知道上面的东西怎么办?
下面说一说使用莫比乌斯函数的O(nlog(n^2))的做法
注:以下讨论均针对于数据加强版,BZOJ上的原题可能不需要这么复杂
最外层先搞一个二分,假设二分到某一个值使得小于等于他的分数刚好有k个
那么我们只需要枚举分母,找到其中最大的一个输出即可
另外,这里的二分只能定分母、二分分子。不能够直接二分小数,原因待会儿说。
考虑到精度问题,我们定分母EPS=1e10(实际上也只能定为1e10,因为小了精度不够,大了要炸long long)
假设二分的分子为k,则现在我们需要求解的便是:\(\sum\limits_{y = 1}^n {\sum\limits_{x = 1}^{\left\lfloor {\frac{{yk}}{{EPS}}} \right\rfloor } {\sum\limits_{d|x,y} {\mu (d)} } } \)
稍微变形一下可以得到:\(\sum\limits_{d = 1}^n {\mu (d)\sum\limits_{y = 1}^{\left\lfloor {\frac{n}{d}} \right\rfloor } {\sum\limits_{x = 1}^{\left\lfloor {\frac{{\left\lfloor {\frac{{y \cdot d \cdot k}}{{EPS}}} \right\rfloor }}{d}} \right\rfloor } 1 } } \)
注意到x的上限有两个取整函数,因为取整函数有这个性质:\(\left\lfloor {\frac{{\left\lfloor {\frac{{\rm{y}}}{a}} \right\rfloor }}{b}} \right\rfloor = \left\lfloor {\frac{y}{{ab}}} \right\rfloor\)
所以才可以去掉上面的那个取整函数,这也是为什么不能直接二分实数,因为实数去不掉那个取整函数
我们继续推导,再次化简以后可以得到:\(\sum\limits_{d = 1}^n {\mu (d)\sum\limits_{y = 1}^{\left\lfloor {\frac{n}{d}} \right\rfloor } {\sum\limits_{x = 1}^{\left\lfloor {\frac{{yk}}{{EPS}}} \right\rfloor } 1 } } \)
这样的话,就可以线性处理后两个Σ,然后O(n)枚举d来计算了
另外还有一个小细节:x不仅受到分数值的限制,还受到n的限制,所以那里还需要特判一下
这题还有一种类似的做法,但可避免炸long long的风险:
考虑仪仗队那个题,因为方队左右对称,于是总可以把问题划归到方阵的右下部分
然后二分右下部分的斜率(定分母为n,二分分子)
二分到分子差只有1的时候,就暴力取出那个区间的所有分数,排序输出
这题我写的代码是第一种方式的,精度巨坑,必须是1e10,且不能有任何实数运算
#include<bits/stdc++.h> #define LL long long #define LD long double using namespace std; const int N = 100000+9; const LL EPS = 1e10; int pri[N],tot,n,cnt,mu[N]; LL f[N],K,vx,vy; bool vis[N]; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } inline void Get_Mu() { mu[1] = 1; for (int i=2;i<=n;i++) { if (!vis[i]) pri[++tot] = i, mu[i] = -1; for (int j=1;j<=tot&&i*pri[j]<=n;j++) { vis[i*pri[j]] = 1; if (i%pri[j]) mu[i*pri[j]] = -mu[i]; else {mu[i*pri[j]] = 0; break;} } } } inline LL Get(LL w) { for (int i=1;i<=n;i++) f[i] = i * w / EPS; for (int i=2;i<=n;i++) f[i] += f[i-1]; LL ret = 0, sta; for (int i=1;i<=n;i++) { sta = (LL)EPS * n / (w * i); ret += f[min(n/(LL)i, sta)] * mu[i]; if (sta < n/i) ret += (n/i) * (n/i - sta) * mu[i]; } return ret; } inline void Get_Ans(LL w) { for (int y=1,x;y<=n;y++) { x = min((LL)n, w * y / EPS); if (x && (vx * y < vy * x || !vx)) vx = x, vy = y; } printf("%lld %lld\n", vx, vy); } int main(){ cin>>n>>K; Get_Mu(); LL l=1, r=(LL)n*EPS, mid, ret; while (l <= r) { mid = l + r >> 1; if (Get(mid) <= K) ret = mid, l = mid + 1; else r = mid - 1; } Get_Ans(ret); return 0; }