https://oj.luyencode.net/problem/FACDIV

[utterances-bot]

Chi tiết bài tập - Luyện Code Online

https://luyencode.net/problem/FACDIV

[tuankietcoderr]

Ối giồi ôi ông Minh ơi ra 10ms thế này thì có phải chết chúng tôi không, cái công thức này nhìn như của số nguyên tố, mà snt tới 10^18 là chua lắm :((

[siroboy]

Định lý Wilson

[siroboy]

tôi tăng time limit lên gấp 3 lần r đấy :v

[ApokPhuoc]

bài này phải 1 s anh ơi :))

[siroboy]

@phuocanh2007 thế thì ra đề này làm chi nữa :')

[namnn17b3]

tóm lại n là số nguyên tố. Nếu check bình thườơng for i <= sqrt(n) -> tle, nếu check qua sàng nguyên tố 10^18 -> rte, chịu hết cách

[siroboy]

@nam29052002 sàng nguyên tố cho dù ko rte cx tle thôi :')

[namnn17b3]

định lý nhỏ fermat và thuật toán Miller cx sai thì chịu :)))

[siroboy]

@nam29052002 có người Accept = Miller r nhé

[goiliace]

5ms là đủ rồi siro ơi

[goiliace]

https://www.geeksforgeeks.org/primality-test-set-3-miller-rabin/ toi an cap code o day

[HaoPham23]

Xài định lý Wilson ổn ko nhỉ, có vẻ sàng ko nổi rồi?

[RoanVanQuyen]

xin test 10 anh em ơi

[RoanVanQuyen]

kiểm tra miller rabin

[khanhduy2311]

nhìn giống định lý wilson thế nhở =)))

[luuquybip]

Đây là lời giải của mình đã AC. Nếu bạn đã cố gắng mà chưa làm được thì có thể tham khảo lời giải của mình.

Xem code AC

```cpp #include using namespace std; typedef long long ll; ll mulmod(ll a, ll b, ll c) { ll x = 0, y = a % c; while (b > 0) { if (b % 2 == 1) x = (x + y) % c; y = (y * 2) % c; b /= 2; } return x % c; } ll modulo(ll a, ll b, ll c) { ll x = 1, y = a; while (b > 0) { if (b % 2 == 1) x = mulmod(x, y, c); y = mulmod(y, y, c); b /= 2; } return x % c; } bool Miller(ll p, int iteration) { if (p < 2) { return false; } if (p != 2 && p % 2 == 0) { return false; } ll s = p - 1; while (s % 2 == 0) { s /= 2; } for (int i = 0; i < iteration; i++) { ll a = rand() % (p - 1) + 1, temp = s; ll mod = modulo(a, temp, p); while (temp != p - 1 && mod != 1 && mod != p - 1) { mod = mulmod(mod, mod, p); temp *= 2; } if (mod != p - 1 && temp % 2 == 0) { return false; } } return true; } int main() { ios::sync_with_stdio(false); cin.tie(0); cout.tie(0); ll n; cin >> n; if (Miller(n, 20)) { cout << "YES"; } else { cout << "NO"; } return 0; } ```

[luuquybip]

Bài khá hay, nhớ thảo luận tớ mới tìm ra những kiến thức diệu kì mới cám ơn nhóm chat

[giabaophudinhthcs]

Lời giải dành cho những bạn chưa giải được: Công thức trên là định lý Wilson. Khi đó n là số nguyên tố. Vậy để kiểm tra số nguyên tố ta dùng định lý Fermat: p là số nguyên tố khi a^(p-1) đồng dư với 1 khi chia cho p. Do đó ta sẽ thử với nhiều a để tăng độ chính xác (từ 100-200 số) kết hợp với phép nhân ấn độ và lũy thừa ấn độ để tăng độ chính xác và giảm được thời gian chạy của chương trình. Code để tham khảo nhé: https://github.com/giabaophudinhthcs/CodingProblem/blob/main/FACDIV.cpp