文文的数学游戏

chen_zhe · 2022-08-07 17:17:40 · 题解

文文的数学游戏

解法

为方便表述，下面令 M=\gcd_{i=1}^n b_i。

对于第一问，M 的最大值即 a_i 中的最小值。因为 g=\gcd(a,b)\leq \min(a,b)。当 M 大于 a_i 中的最小值，则存在至少一个 i 使得 b_i \leq a_i<M，此时 \gcd(M,a_i)<M。而当 M 取到 a_i 中的最小值 a_{\min} 可以让 b_i 全部取到 a_{\min}，这样就可以使得 M 最大。

有多少种取法？令 b_i=a_{\min},2a_{\min},\dots,na_{\min}(b_i \leq a_i) 都是不会改变 M 的。考虑 a_{\min} 前面的系数最大值 d_i，则 d_i=\lfloor \dfrac{a_i}{a_{\min}}\rfloor。由于可以对每个 b_i，任取 b_i=c\times a_{\min}(c \in [1,d_i])，则取法的答案为 \prod \limits_{i=1}^n d_i。记得开 long long，以及边乘边取模。

#include <iostream>
using namespace std;
int a[100050],n,mgcd=1<<30;
const int mod=1e9+7;
int main()
{
    cin >> n;
    for (int i=1;i<=n;i++)
    {
        cin >> a[i];
        mgcd=min(mgcd,a[i]);
    }
    long long ans=1;
    for (int i=1;i<=n;i++)
        ans=(long long)ans*(a[i]/mgcd)%mod;
    cout << mgcd << " " << ans << endl;
    return 0;
}