Ta biến đổi phương trình trên cho dễ dùng thành `((n^p)% p + n%p)%p = 0` như vậy ta lấy `n = 2` và xử lý riêng trường hợp `p = 2`
=> `((n^p)%p + n)%p = 0`
Ta chỉ việc xử lý `n^p` thông qua phép chia để chị mất `log2(a)` kết hợp với tính chất mod trong phép nhân. Ta dễ dàng tính được khi dùng kiểu dữ liệu `unsigned long long` tính giá trị `a <= 2^32`
Để tính giá trị a lớn hơn (a <= 2^53) ta sẽ lại dùng chia để chị và tính chất mod cho phép cộng để tính (a*b) hỗ trợ cho phép tính hàm mũ
Như vậy ta đã có thuật toán O(n log(a)^2), các bạn có hể tham khảo code ở dưới
Tham khảo code của
Sơn Đẹp Zai
// _____ _ _ // / ____| | | (_) // | (___ ___ _ __ __| | ___ _ __ ______ _ _ // \___ \ / _ \| '_ \ / _` |/ _ \ '_ \ |_ / _` | | // ____) | (_) | | | | | (_| | __/ |_) | / / (_| | | // |_____/ \___/|_| |_| \__,_|\___| .__/ /___\__,_|_| // | | // |_|#include <bits/stdc++.h> #define nmax 100005 #define oo 10000000007 #define mod 1000000007 #define reset(x) memset(x, 0, sizeof x) #define PB(x) push_back(x) #define F first #define S second #define sonin cin #define sonout cout #define debug(x) cout << "Loli -> " << #x << " : " << x << "\n" #define debugAry(x, a, b, y) for(int y = a; y<=b; y++) cout << #x << "[" << y << "]" << " -> " << x[y] << "\n" #define filename "testnguyento" #define fileNX freopen(filename".inp", "r", stdin); freopen(filename".out", "w", stdout); #define fileN freopen(filename".inp", "r", stdin); #define fileX freopen(filename".out", "w", stdout); #define toiuuhoa ios::sync_with_stdio(0);cin.tie(0);cout.tie(0); #define SZ(a) (int) a.size() #define FOU(x,a,b) for (lli x=a;x<=b;x++) #define FOD(x,a,b) for (lli x=a;x>=b;x--) #define FOA(a,b) for(auto &a:b) #define ALLvec(a) a.begin(),a.end() #define REU(x,a,b) for (lli x=a;x<b;x++) #define RED(x,a,b) for (lli x=a;x>b;x--) #define AutoCinAry(a,b,x) for(int a = 1; a<=b; a++) cin >> x[i]; #define dembit1(x) __builtin_popcount(x) #define bit(x,i) ((x>>(i-1))&1ll) #define on(x,i) (x|(1ll<<(i-1))) #define off(x,i) (x&~(1ll<<(i-1))) #define EL cout << "\n"; #define EX exit(0); #define Ary(x, i, j, a) x[(i - 1) * a + j] #define epsinon 1e-8 #define Son_onii_chan main #define times double stime = clock(); #define gettime cerr << "Time executed: " << (clock() - stime) / CLOCKS_PER_SEC * 1000 << "ms.\n"; using namespace std; typedef long long lli; typedef long double ldo; typedef double dou; typedef vector vi; typedef vector vvi; typedef pair<lli, lli> pii; typedef vector vpi; typedef deque dqll;
lli mulmodu64(lli a, lli b, lli m) { a %= m; b %= m; if (a == 0) return 0; if (b <= numeric_limits::max() / a) return (a*b) % m; lli res = 0; while (a != 0) { if (a & 1) { if (b >= m - res) res -= m; res += b; } a >>= 1; if (b >= m - b) b += b - m; else b += b; } return res; } lli powlc(lli ac, lli bc, lli modb) { lli cc; if (bc == 0) return 1; if (bc == 1) return (ac % modb); cc = powlc(ac, bc / 2, modb) % modb; cc = mulmodu64(cc, cc, modb) % modb; if (bc % 2) cc = mulmodu64(cc, ac, modb); return (cc % modb); }
lli p; void checknguyento1(){ if (p == 2) { sonout << "1"; } else { if (((powlc(2, p, p) - (2 % p)) % p) == 0){ sonout << "1"; } else sonout << "0"; } EL }
int Son_onii_chan() { toiuuhoa FOU(jj, 1, 100000){ sonin >> p; checknguyento1(); } return 0; }
Tổng cộng 2 trả lời
Dùng miller rabin là ăn nhénhé
vẫn có nhiều trường hợp sai khi input là pseudoprime như 645 :/