题解 P4905 【报纸】

· · 题解

不好意思，之前代码交错了，代码中会标出。导致很多抄题解的全是90，哈哈哈

嗯~n才233不大，可以用n（2）笨蛋。 先用gcd把图建好，再按照每个点一次判断四周有没有需要拍的就好。

#include<bits/stdc++.h>
#define maxn 255
using namespace std;
int n,ans;
bool vis[maxn][maxn],a[maxn][maxn];
inline int read(){
    int ret=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9'){if (ch=='-') f=-f;ch=getchar();}
    while (ch<='9'&&ch>='0') ret=ret*10+ch-'0',ch=getchar();
    return ret*f;
}
inline int gcd(int x,int y){
    if (!y) return x;
    return gcd(y,x%y);
}
int main(){
    n=read();
    for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++) if (gcd(i,j)!=1) a[i][j]=1;
    for (int i=1;i<=n;i++)
    for (int j=1;j<=n;j++){
        if (a[i][j]&&!vis[i][j]){
            ans++;
            if (a[i+1][j]&&!vis[i+1][j]) vis[i+1][j]=1;
            /*else*/ if (a[i][j+1]&&!vis[i][j+1]) vis[i][j+1]=1;
            //else不能加，之前就是错在这，因为一个点可以多次拍照
        }
    }
    printf("%d",ans);
    return 0;
}