题解 CF194B 【Square】

## 题目大意 一个边长为$n$的正方形广场。现在沿着广场的边缘，每走$n+1$个单位就会画一个十字，直到在起点处又画了一个十字。询问一共画了多少个十字。 ## 题解 一道比较简单的数学题……其实并不需要找规律也能很容易地写出来。 显然，正方形广场的边长为$4\times n$。也就是说，我们要计算出最小的$m$，使得 $$m\times (n+1)\equiv 0\pmod{4\times n}$$ 换句话说，假设我们绕着广场走了$k$圈，就有 $$m\times (n+1)=k\times 4\times n$$ 经过移项，可得： $$m=\frac{k\times 4\times n}{n+1}$$ 我们就是要求出使得这个分数为正整数的最小的正整数$k$。显然$n$与$n+1$互质。我们可以讨论$n+1$与$4$的关系。若互质，则$k=n+1$；若$4|n+1$，则$k=\frac{n+1}{4}$。若$4$与$n+1$有一个公因数$2$，则$k=\frac{n+1}{2}$。 答案就是$m+1$。 ## 参考代码 ``` #include<bits/stdc++.h> #define up(l,r,i) for(int i=l;i<=r;i++) #define dn(l,r,i) for(int i=l;i>=r;i--) using namespace std; typedef long long LL; const int INF =2147483647; int qread(){ int w=1,c,ret; while((c=getchar())> '9'||c< '0') w=(c=='-'?-1:1); ret=c-'0'; while((c=getchar())>='0'&&c<='9') ret=ret*10+c-'0'; return ret*w; } int n,k; int main(){ dn(qread(),1,T){ n=qread(); if((n+1)%4==0) k=(n+1)/4; else if((n+1)%2==0) k=(n+1)/2; else k=n+1; printf("%lld\n",((LL)k*4*n)/(n+1)+1); } return 0; } ```