题解：P13635 [NWRRC 2021] Halfway There

Lsy_er13 · 2025-10-08 13:06:14 · 题解

我和楼上的方法差不多，但我优化了一些特殊情况。

题意

求小于 n 的所有与 n 互质的数集合中的中位数。

分析

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\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;
  }

  完结撒花！求赞。