题解：P13635 [NWRRC 2021] Halfway There

题意

分析

1. $n$ 为奇数。

• 由于 $n$ 是奇数,所以 $(n-1)\div2$ 和 $n$ 互质。
• 证明：设 $(n-1)\div2$ 为 $k$。
  $\gcd(n,k)=\gcd(2\times k+1,k)=\gcd(k,1)=1$
  所以 $(n-1)\div2$ 和 $n$ 互质。
• 因此中位数直接就是 $(n+1)\div2$ 或直接 $n\div2$。

2. $n$ 是 $2$ 的幂。

• $n$ 只有质因数 $2$。
• 中位数是 $n\div2-1$。

3. $n$ 是偶数但不是 $2$ 的幂。

• 我们从 $n\div2$ 开始向下检查，找到第一个与 $n$ 互质的最大整数。
• 因为 $\gcd(a,b)=\gcd(a,a-b)$，所以与 $n$ 互质的数是成双成对的，所以这个数就是我们要找的中位互质数。

代码：

#include<bits/stdc++.h>
using namespace std;
int t;
long long hs(long long x){
    if(x%2==1)return x/2;//n为奇数情况
    if(x&(x-1)==0)return x/2-1;//n为2的幂的情况
    for(long long i=x/2;i>=1;i--){
        if(__gcd(i,x)==1)return i;
    }return 1;//因为数据n>=2,所以可写可不写。
}
int main(){
    cin>>t;
    while(t--){
        long long n;
        cin>>n;
        cout<<hs(n)<<endl;
    }
    return 0;
}