【题解】绝对值的故事
题意
给你一个长度为的数组
,求数组中元素两两之差的绝对值之积。但是乘积可能会很对,所以对
进行取模后输出。
题解
先看数据范围,由于较大,但是模数
较小。根据鸽巢原理\抽屉原理,当
比
大时,必存在两个元素对
取模后相等,也因为
。所以可以认为当
大于
时,答案肯定为
。那么对于
小于
的部分我们只用去模拟运算一遍即可。
复杂度
时间复杂度或
代码
#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int a[N]; int main() { int n,m; long long ans = 1; scanf("%d%d",&n,&m); for(int i = 1; i <= n; i++) scanf("%d",&a[i]); if(n > m) { printf("0\n"); return 0; } for(int i = 1; i <= n-1; i++) { for(int j = i+1; j <= n; j++) { ans=ans*abs(a[i]-a[j])%m; } } printf("%lld\n",ans); return 0; }