AtCoder - 4172 Modulo Summation 贪心

开始想复杂的了 仔细观察样例后发现这个数 其实就是所有的数的LCM-1吗

只有LCM-1 对所有数取模的时候才能对所有数得到MOD = a[i]-1；

那么一个X%Y得到的最大值就是Y-1

于是得到了这个代码

#include<iostream>
#include<cstdio>
#include<queue>
#include<cstring>
#include<algorithm>
#include<vector>
#include<map>
#include<sstream>
typedef long long LL;
using namespace std;

LL a[3010];
LL Gcd(LL A,LL B){
    return B==0?A:Gcd(B,A%B);
}
int main()
{
    int n;
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        scanf("%lld",&a[i]);
    LL s = a[1];
    for(int i = 2;i<=n;i++){
    
        LL gcd = Gcd(s,a[i]);
        s = s/gcd*a[i];
    }

    s--;
    LL sum=0;
    for(int i=1;i<=n;i++){
        sum+=s%a[i];
    }
    printf("%lld\n",sum);
    return 0;
}
           

我呢 就真的按照分析好的思路去实现了 求一遍所有数的LCM 然后-1 在逐个取模

然后轻而易举的WA 了