[CodeForces - 1305C] - Kuroni and Impossible Calculation [동여+비둘기 둥지]

[CodeForces - 1305C] - Kuroni and Impossible Calculation
제목:

길이가 n인 서열에서 우리는 임의의 두 수차의 절대값을 얻을 수 있다. 모든 절대값을 곱해서 m에 대한 모형을 추출한 결과는?

아이디어:
(1) 동여정리:
a ≡ b (m o d m) a\equiv b (mod\m) a ≡ b (mod m) 그러면 (a - b) ≡ 0 (m o d m) (a - b)\equiv 0 (mod\m) (a - b) ≡ 0 (mod m)
(2) 비둘기 둥지 원리(서랍 원리)
사과 열 개를 아홉 서랍에 넣으면 아무리 놓아도 한 서랍에 사과 두 개가 있다.

상기 두 가지 정리를 이용한다.우리는 쉽게 얻을 수 있다. 만약에 n>m라면 총 두 개의 수가 m에 대해 동여이기 때문에 마지막 곱셈도 항상 0이다.반대로 n<=m, 그러면 범위는 1000, 폭력으로 해답을 구하면 됩니다.

#include 
using namespace std;
typedef long long ll;
inline int read()
{
    int x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') { if(c == '-') f = -f; c = getchar(); }
    while(c >= '0' && c <= '9') { x = x * 10 + c - '0'; c = getchar(); }
    return x * f;
}

const int maxN = 200005;

int n, m, a[maxN];

int main()
{
    n = read(); m = read();
    for(int i = 0; i < n; ++ i )
        a[i] = read();
    if(n > m)
        cout << "0
";
    else
    {
        ll ans = 1;
        for(int i = 0; i < n; ++ i)
            for(int j = i + 1; j < n; ++ j )
                ans = ans * abs(a[i] - a[j]) % m;
        cout <<  ans % m << endl;
    }
    return 0;
}

이 내용에 흥미가 있습니까?

현재 기사가 여러분의 문제를 해결하지 못하는 경우 AI 엔진은 머신러닝 분석(스마트 모델이 방금 만들어져 부정확한 경우가 있을 수 있음)을 통해 가장 유사한 기사를 추천합니다:

문제 풀이 보고서 의 CodeForces 91B Queue

Otherwise, print the i-th walrus's displeasure: the number of other walruses that stand between him and the furthest fro...

텍스트를 자유롭게 공유하거나 복사할 수 있습니다.하지만 이 문서의 URL은 참조 URL로 남겨 두십시오.

CC BY-SA 2.5, CC BY-SA 3.0 및 CC BY-SA 4.0에 따라 라이센스가 부여됩니다.

[CodeForces - 1305C] - Kuroni and Impossible Calculation [동여+비둘기 둥지]

좋은 웹페이지 즐겨찾기