题解 CF194B 【Square】
囧仙
2020-05-21 20:46:00
## 题目大意
一个边长为$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;
}
```