自动搬运

查看原文

来自洛谷，原作者为

	gaoyangyang 藿藿真是太可爱啦！！！

搬运于2025-08-24 22:05:08，当前版本为作者最后更新于2023-07-25 10:58:22，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

因为本题数据并不会很大只有 233 ，所以可以用打表的方式做：

打表思路：

首先写一个判断互质的函数（返回值 $1$ ：不互质；$0$ ：互质）。

int hz(int a,int b)
{
	for (int i=2;i<=min(a,b);i++)
	{
		if  (a%i==0 and b%i==0)
		{
			return 1;
		}
	}
	return 0;
   //例如：当我输入4时，他会产生：
   	//2 2
	//2 4
	//3 3
	//4 2
	//4 4
   //一共五个非互质数对
}

接下来将互质的数对可视化。

int hz(int a,int b)
{
	for (int i=2;i<=min(a,b);i++)
	{
		if  (a%i==0 and b%i==0)
		{
			return 1;
		}
	}
	return 0;
}
int a[1000][1000];
int n;
int main()
{
	cin>>n;
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
		{
			if (hz(i,j))
			{
				a[i][j]=1;
			}
		}
	}
	for (int i=1;i<=n;i++)
	{
		for (int j=1;j<=n;j++)
		{
			cout<<a[i][j]<<" ";
		}
		cout<<endl;
	}
	return 0;
   //例如：当我输入4时，会输出：
   	//0 0 0 0
	//0 1 0 1
	//0 0 1 0
	//0 1 0 1
   //这一个矩阵即题目中有答案的地方
}

然后运用“自然有机分子运算器”（大脑）开始打表。

这里以输入样例：$6$ 为例。

首先，生成有“答案”的坐标二维表。

可得：

接下来以有“ $1$ ”的点开始 向外扩展（只有两种方向：右或下，尽量多的覆盖没有被覆盖的标记点）。 所以输入为 $6$ 的矩阵就可以这样填充（数字为编号，这里为方便展示将原本的标记“ $1$ ”改为@）填法不唯一。

刚刚好 $11$ 个。

接下来加亿点肝量（耗时数周）可得出答案。 下面亮代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
	int n;
	//暴力出奇迹，打表得省一 
	int a[234]={0,1,2,5,6,11,12,19,22,31,32,43,44,57,64,79,80,97,98,117,126,147,148,171,176,201,210,237,238,267,268,299,312,345,356,391,392,429,444,483,484,525,526,569,590,635,636,683,690,739,758,809,810,863,880,933,954,1011,1012,1071,1072,1133,1160,1223,1240,1305,1306,1373,1398,1467,1468,1539,1540,1613,1648,1723,1740,1817,1818,1897,1924,2005,2006,2089,2112,2195,2226,2313,2314,2403,2424,2513,2546,2639,2662,2757,2758,2855,2894,2993,2994,3095,3096,3199,3256,3361,3362,3469,3470,3579,3618,3729,3730,3843,3870,3985,4030,4147,4170,4289,4300,4421,4464,4587,4612,4737,4738,4865,4910,5039,5040,5171,5196,5329,5392,5527,5528,5665,5666,5805,5854,5995,6018,6161,6194,6339,6402,6549,6550,6699,6700,6851,6908,7061,7096,7251,7252,7409,7464,7623,7652,7813,7814,7977,8062,8227,8228,8395,8408,8577,8640,8811,8812,8985,9046,9215,9276,9453,9454,9633,9634,9815,9878,10061,10102,10287,10314,10501,10582,10771,10772,10963,10964,11157,11256,11451,11452,11649,11650,11849,11918,12119,12154,12357,12404,12607,12682,12889,12918,13127,13128,13339,13412,13625,13672,13887,13924,14141,14216,14435,14464,14685,14686,14909,15014,15239,15240,15467,15468,15697,15808,16039,16040};
	cin>>n;
	cout<<a[n-1]<<endl;
}