Chia hết - LCOJ: Luyện Code Online Judge

FACDIV - Chia hết

Điểm: 1,00 (OI)

Giới hạn thời gian: 0.5s

Giới hạn bộ nhớ: 256M

Tác giả:

siro

Dạng bài

Ngôn ngữ cho phép

C, C#, C++, Go, Java, Pascal, Perl, PHP, PyPy, Python, Ruby, Rust, Scratch, Swift

Cho số nguyên dương ~n~, hãy cho biết ~L = (n - 1)! + 1~ có chia hết cho ~n~ không?

Input

Ghi số nguyên dương ~n (1 \le n \le 10^{18})~.

Output

Nếu ~L~ chia hết cho ~n~ thì in ra YES, ngược lại thì in ra NO.

Sample

Input #1

Output #1

YES

Input #2

Output #2

NO

Hint

Giải thích #1: ~L = 1 * 2 + 1 = 3~ -> ~L~ ~mod~ ~3 = 0~.

Bình luận

Please read the guidelines before commenting.

include <bits/stdc++.h>

using namespace std;

// Modular multiplication to avoid overflow long long mulMod(long long a, long long b, long long mod) { int128 result = (int128)a * b % mod; return (long long)result; }

// Modular exponentiation long long powMod(long long a, long long d, long long mod) { long long result = 1; a %= mod; while (d > 0) { if (d & 1) result = mulMod(result, a, mod); a = mulMod(a, a, mod); d >>= 1; } return result; }

// Deterministic Miller-Rabin for 64-bit integers bool isPrime(long long n) { if (n < 2) return false;

// Small primes check
for (long long p : {2, 3, 5, 7, 11, 13, 17, 19, 23, 29}) {
    if (n % p == 0) return n == p;
}

// Write n-1 = d * 2^s with d odd
long long d = n - 1;
int s = 0;
while (d % 2 == 0) {
    d /= 2;
    s++;
}

// Deterministic bases for n < 2^64
vector&lt;long long> bases;
if (n < 341550071728321LL) {
    bases = {2, 3, 5, 7, 11, 13, 17};
} else {
    bases = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37};
}

for (long long a : bases) {
    if (a >= n) continue;
    long long x = powMod(a, d, n);
    if (x == 1 || x == n - 1) continue;

    bool composite = true;
    for (int r = 1; r < s; r++) {
        x = mulMod(x, x, n);
        if (x == n - 1) {
            composite = false;
            break;
        }
    }
    if (composite) return false;
}
return true;

}

int main() { //freopen("FACDIV.INP", "r", stdin); //freopen("FACDIV.OUT", "w", stdout);

long long n;
cin >> n;

if (n == 1 || isPrime(n)) {
    cout << "YES\n";
} else {
    cout << "NO\n";
}

return 0;

}

-2

VuSiSi đã bình luận lúc 23, Tháng 11, 2024, 12:07

sử dụng định lý wilson

-4

kien đã bình luận lúc 16, Tháng 8, 2023, 16:50

chỉnh lại thời gian limit