自动搬运

查看原文

来自洛谷，原作者为

	chen_zhe Aya 敲可爱的~

搬运于2025-08-24 22:39:20，当前版本为作者最后更新于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;
}