Ozon Tech Challenge 2020 (Div.1+Div.2) C. Kuroni and Impossible Calculation

 

이런 수학문제가 참 어려운거같다 나는

한참 생각하고 틀린 문제다 혼자 식을 줄이려고 애썼는데 안떠오른다..

 

이 문제는 m이 1000이하인게 힌트다!

 

먼저 2가지 경우가 있을 수 있다

 

1. n<=m인 경우

그럼 n의 최댓값이 1000이므로 그냥 n^2으로 직접 구해보면 된다

그래봐야 백만이다!!

 

2. n>m인 경우

이 경우를 생각도 못했다. 만약 n>m이라면 어떻게 될까?

%m해서 나올 수 있는 값은 총 m개다 근데 m보다 큰 n에 대해 %m을 한다면

비둘기집의 원리에 의해 누군가 하나는 같은게 나올 수 밖에 없다!! 생각도못함..!

같은게있다는말은 빼면 0이된다는 말이고 결국 곱하기 0이 생긴다는거니까 0이다 그냥!

그냥 0..!

 

수학공부를 다시 해야할까보다..

 

소스코드

#include <bits/stdc++.h>
using namespace std;
#define ll long long
int n,m;
int arr[200020];
 
int main(){
    scanf(" %d %d",&n,&m);    
    for(int i=0;i<n;i++) scanf(" %d",&arr[i]);
    
    if(n>m) puts("0");
    else{
        ll ans=1LL;
        for(int i=0;i<n;i++){
            for(int j=i+1;j<n;j++){
                ans*=abs((ll)arr[j]-(ll)arr[i]);
                ans%=(ll)m;
            }
        }
        printf("%lld\n",ans);
    }
}