P4905的题解

gaoyangyang · 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;
}