（被撤下）题解：SP30396 GCDEASY - Easy GCD

· · 题解

题意翻译：

给你一个数列 A，你需要求出他们的最大公约数 a，然后找到最大的 b 满足 0\leq b\leq k 且 a,b 不互质。

题目保证 a\not =1。本题有多组数据。

本题考查：

分析

首先考虑求出 a，我使用的是辗转相除法。

inline int gcd(int a,int b){
    if(b==0)return a;
    else return gcd(b,a%b); 
}

如果你嫌麻烦，可以使用 __gcd(,)。

此处的单组数据复杂度为 O(n\log{v})（v 为值域）。

然后考虑求出 b。

发现如果两个数不互质的话，其必定有一个公因子大于 1。

从这方面下手，选取每一个 a 的非 1 因子 c，求出其最大的 b=c\cdot \lfloor\frac{k}{c}\rfloor。

代码实现如下：

inline int getb(int a,int k){
    int b=0;
    for(int i=2;i<=a;i++){
        if(a%i==0)b=max(k/i*i,b);
    }
    return b;
}

此处的复杂度是 O(\sqrt{v})。

总结：

本题较简单，可以作为数论的入门题目。

code：

#include<bits/stdc++.h>
using namespace std;
const int N=1e5+5;
int n,A[N],k,T;
inline int gcd(int a,int b){
    if(b==0)return a;
    else return gcd(b,a%b);
}
inline int getb(int a,int k){
    int b=0;
    for(int i=2;i<=a;i++){
        if(a%i==0)b=max(k/i*i,b);
    }
    return b;
}
inline void solve(){
    cin>>n>>k;
    for(int i=1;i<=n;i++)cin>>A[i],A[i]=gcd(A[i],A[i-1]);
    cout<<getb(A[n],k)<<'\n';
}
int main (){
    ios::sync_with_stdio(0);
    cout.tie(0);cout.tie(0);
    cin>>T;
    while(T--)solve();
    return 0;   
}