P4905 报纸

Coros_Trusds · 2021-11-27 22:10:32 · 题解

题目大意

给定一个 n，表示有一个 n\times n 的矩阵 a。

题目分析

前置知识：

欧几里得算法求两数最大公因数：

inline int gcd(int a,int b){
    if(!b)return a;
    return gcd(b,a%b);
} 

我们暴力预处理出 n\times n 的矩阵中，i,j 不互质的点，1\le i,j\le n。

如果当前写有答案（即不互质）并且当前还没有访问过，那么访问之，令当前坐标为 (i,j)，那么判断 (i,j) 和 (i+1,j) 以及 (i,j) 和 (i,j+1) 是否有答案，如果有，那么拍下它。

发现 n\le 233，可以通过。

代码

const int ma=235;

bool mp[ma][ma],vis[ma][ma];

int n;

inline int gcd(int a,int b)
{
    if(b==0)
    {
        return a;
    }

    return gcd(b,a%b);
} 

int main(void)
{
    n=read();

    for(register int i=1;i<=n;i++)
    {
        for(register int j=1;j<=n;j++)
        {
            if(gcd(i,j)!=1)
            {
                mp[i][j]=true;
            }
        }
    }

    int ans(0);

    for(register int i=1;i<=n;i++)
    {
        for(register int j=1;j<=n;j++)
        {
            if(mp[i][j]==true && vis[i][j]==false)
            {
                ans++;

                if(mp[i+1][j]==true && vis[i+1][j]==false)
                {
                    vis[i+1][j]=true;
                }

                if(mp[i][j+1]==true && vis[i][j+1]==false)
                {
                    vis[i][j+1]=true;
                }
            }
        }
    }

    printf("%d\n",ans);

    return 0;
}