第一道黑题居然是 NOI 的题。
题意分析
显然，$f(i,j)=f(j,i)$，因此可以假定 $n\leq m$。（否则交换 $n,m$）。
生成方式唯一
假设 $x\in S$，则从 $2$ 开始生成，$x$ 的最短生成方式是唯一的。
证明
由 $S$ 性质可得：
- $\dfrac1x\in S$。
- $x+2k\in S$。
这可以等价于：
- $\dfrac{1}{x+2k}\in S$。
其中，$k\in \mathbb Z$，且 $x+2k>0$。
则，$x$ 可以表示为连分数：
\[x=\dfrac{1}{\dfrac{1}{\dfrac{\begin{aligned}\cdots\end{aligned}}{\dfrac{1}{2+2k_1}+2k_2}+\cdots}+2k_n}\]令 $x$ 的最短生成方式不唯一，设两种方式的增加数为 $k_i,k’_i$。
可以使用数学归纳法证明。
考虑到 $n=1$ 时，有：
\[\dfrac{1}{2+2k_1}=\dfrac{1}{2+2k'_1}\]交叉相乘，得到：
\[2+2k_1=2+2k'_1\]必有 $k_1=k’_1$，即操作次数为 $1$ 的 $x$ 的最短生成方式唯一。
可以发现，一个连分数对应一个生成出来的元素。
假设 $\dfrac{1}{2+2k_i},\dfrac1{2+2k’_i}$ 对应同一个元素 $y$，从 $y$ 走出的元素操作 $1$ 次到了同一个元素 $x$，生成方式必然相同，则 $n=i+1$ 时也成立。
故，生成方式唯一。
DFS 搜索
可以发现，不需要取模。那么要么是毒瘤题写高精度，要么是答案不多。
因此可以考虑复杂度与答案相关的算法——搜索。
设当前搜索分式中 $k_i$ 的最大值为 $\textit{Max}$。
则连分式可以被表示为 $\dfrac{a\cdot\textit{Max}+b}{c\cdot\textit{Max}+d}$。
连分式： \(x=\dfrac{1}{\dfrac{1}{\dfrac{\begin{aligned}\cdots\end{aligned}}{\dfrac{1}{2+2k_1}+2k_2}+\cdots}+2k_i}\) 设当前元素为第 $i$ 项。
当前状态 $x_i>1$ 的部分对答案 $\textit{ans}$ 的贡献即 $\begin{cases}a\cdot x_i+b\leq n\c\cdot x_i+d\leq m\x_i\geq Max\end{cases}$ 的解的数量。
$x_i<1$ 的部分对答案 $\textit{ans}$ 的贡献即 $\begin{cases}c\cdot x_i+d\leq n\x_i\geq \textit{Max}\end{cases}$ 的解的数量。
AC 代码
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
//#include<bits/stdc++.h>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<iomanip>
#include<cstdio>
#include<string>
#include<vector>
#include<cmath>
#include<ctime>
#include<deque>
#include<queue>
#include<stack>
#include<list>
using namespace std;
typedef long long ll;
constexpr const int N=3e7,M=3e7;
int n,m;
ll ans;
template<typename T>
T divide(T a,T b){
if(!b){
return 2147483647;
}
return a/b;
}
//统计具体答案
void dfs(int a,int b,int c,int d,int Max){
if(1ll*a*Max+b>n){
return;
}
ans+=max(0 , min( divide(n-b,a) ,divide(m-d,c) ) - Max + 1);
ans+=max(0 , divide(n-d,c) - Max + 1);
for(int x=1;;x++){
int down=max(Max,x+1);
int A=2*c*x+a,B=2*d*x+b;
if(1ll*A*down+B>m){
break;
}
dfs(c,d,A,B,down);
}
}
//搜索连分式
void dfs2(int a,int b,int Max){
for(int x=1;;x++){
int down=max(Max,x);
ll pl=2ll*x*b+a;
if(2ll*pl*down+b>m){
break;
}
dfs2(b,pl,down);
}
dfs(0,b,2*b,a,Max);
}
int main(){
/*freopen("test.in","r",stdin);
freopen("test.out","w",stdout);*/
ios::sync_with_stdio(false);
cin.tie(0);cout.tie(0);
cin>>n>>m;
if(n>m){
swap(n,m);
}
dfs2(0,1,1);
cout<<ans<<'\n';
cout.flush();
/*fclose(stdin);
fclose(stdout);*/
return 0;
}
