题解 | #[NOIP2017]小凯的疑惑#

这是一道数论题，正如各位大佬所讲。

看到这道题，我首先想的就是打表。但是数据太大，显然打表占用空间太多。

但是，我们可以打一个小一点的表，比如$20\times 2020\backslash times20$（点表示$\gcd (a,b)\mathrm{\ne }1\backslash gcd(a,b)\backslash neq1$）：

然后整齐的等差数列成功地引起了注意。我们可以把等差数列补全，如第四行变为了：

$258111417\cdots 562\backslash qquad5\backslash qquad8\backslash qquad11\backslash qquad14\backslash qquad17\backslash qquad\backslash cdots\backslash qquad56$

Very Nice！首项$v_1=a-2v\_\{1\}=a-2$，公差$d=a-1d=a-1$，要求的项是$v_{b-1}v\_\{b-1\}$；根据小学时学的等差数列求第$nn$项的公式：$v_n=v_1+(n-1)dv\_\{n\}=v\_\{1\}\; +\; (n-1)d$，再把数带进去：$v_{b-1}=(a-2)+(b-2)(a-1)=(a-1)(b-1)-1v\_\{b-1\}=(a-2)+(b-2)(a-1)=(a-1)(b-1)-1$，那么代码就简单了：

#include <bits/stdc++.h>
using namespace std;
#define int long long
int a, b;
signed main(){
	cin >> a >> b;
	cout << (a - 1) * (b - 1) - 1 << endl;
	return 0;
}

注意：一定要开long long！

因为：

对于 $30\mathrm{\%}30\backslash \%$ 的数据：$1\le a,b\le 501\; \backslash leq\; a,b\; \backslash leq\; 50$;

对于 $60\mathrm{\%}60\backslash \%$ 的数据：$1\le a,b\le 10^{4}1\; \backslash leq\; a,b\; \backslash leq\; 10^4$;

对于 $100\mathrm{\%}100\backslash \%$ 的数据：$1\le a,b\le 10^{9}1\; \backslash leq\; a,b\; \backslash leq\; 10^\{9\}$。