Codeforces Round #651 (Div. 2) A. Maximum GCD

A. Maximum GCD

题目链接-A. Maximum GCD

题目大意
给你一个数$n$n，在$1—n$1—n的所有不同整数对中，找出成对整数的最大公约数的最大值，即求$gcd(a，b)$gcd(a，b)的最大值$(1≤a<b≤n)$(1≤a<b≤n)

解题思路

• 如果$n$n为偶数，那么$gcd(a,b)$gcd(a,b)的最大值必然是$gcd(n/2,n)$gcd(n/2,n)，即最大值为$n/2$n/2
• 如果$n$n为奇数，根据上一条$n$n为偶数的情况，$1—n$1—n的最大偶数为$n-2$n−2，显然$gcd(a,b)$gcd(a,b)的最大值必然是$gcd((n-1)/2,n-1)$gcd((n−1)/2,n−1)，即最大值为$(n-1)/2$(n−1)/2
• 因为C/C++中的整数除法运算本身就有取整功能，即向下取整，所以这道题的答案就为$n/2$n/2

附上代码

#pragma GCC optimize("-Ofast","-funroll-all-loops")
#include<bits/stdc++.h>
#define int long long
#define lowbit(x) (x &(-x))
#define endl '\n'
using namespace std;
const int INF=0x3f3f3f3f;
const int dir[4][2]={-1,0,1,0,0,-1,0,1};
const double PI=acos(-1.0);
const double e=exp(1.0);
const double eps=1e-10;
const int M=1e9+7;
const int N=2e6+10;
typedef long long ll;
typedef pair<int,int> PII;
typedef unsigned long long ull;
inline void read(int &x){
    char t=getchar();
    while(!isdigit(t)) t=getchar();
    for(x=t^48,t=getchar();isdigit(t);t=getchar()) x=x*10+(t^48);
}
signed main(){
	ios::sync_with_stdio(false);
	cin.tie(0);cout.tie(0);

	int t;
	cin>>t;
	while(t--){
		int n;
		cin>>n;
		cout<<n/2<<endl;
	}
	return 0;
}