COFO::1305C Kuroni and Impossible Calculation

• Link : COFO::1305C

Problem

• level : 1600
• tag : brute force, combinatorics, math, number theory
• TIME
  • to understand :
  • to algorithm : fail
  • to code :
  • to debug :
  • understanding edit and solve with edit: 10
  • Tried to solve the problem before read edit : 50

Point

• array a is given
• find the remainder of products of any pairs

Design

• This problem is incredible
• The thing is that
  • When n is less than m, we can do brute force obviously
  • When n is greater than m, then the answer is 0
    • There can be two kinds of cases for this
      • When there are n distinct numbers in the array a
        • Then, since n is greater than m, at least one of the pairs would be 0

        • x - y

          = 0

      • When there are less than n distinct numbers, which means there are same numbers then

        • x - y

          = 0

Complexity

• O(M^2)

Code

#include<bits/stdc++.h>
#define fi first
#define se second
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define rep(i, a, b) for(int i = (a); i <(b); i++)
#define r_rep(i, a, b) for(int i = (a); i >(b); i--)
typedef long long ll;
using namespace std;

void solve() {
    int n, m; cin >> n >> m;
    vector<int> a(n); rep(i, 0, n) cin >> a[i];
    
    if (n > m) {cout << "0\n"; return;}
    
    bool f = false;
    ll ans = 0;
    rep(i, 0, n ) {
        rep(j, i + 1, n) {
            if (!f) ans = abs(a[i] - a[j]);
            else ans *= abs(a[i] - a[j]);
            ans %= m;
            f = true;
        }
    }
    cout << ans << '\n';
}
int main(){
    ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL);
    
    //int tc; cin >> tc; while(tc--)
    solve();
    return 0;
}