网站建设与维护课程,佛山网站建设企业,注册会计师,88黄页企业名录开始想复杂的了 仔细观察样例后发现这个数 其实就是所有的数的LCM-1吗
只有LCM-1 对所有数取模的时候才能对所有数得到MOD = a[i]-1；
那么一个X%Y得到的最大值就是Y-1
于是得到了这个代码
#includeiostream
#includecstdio
#includequeue
#includ…开始想复杂的了 仔细观察样例后发现这个数 其实就是所有的数的LCM-1吗
只有LCM-1 对所有数取模的时候才能对所有数得到MOD = a[i]-1；
那么一个X%Y得到的最大值就是Y-1
于是得到了这个代码
#includeiostream
#includecstdio
#includequeue
#includecstring
#includealgorithm
#includevector
#includemap
#includesstream
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 了
