C++Kiểm tra số nguyên tố O(log(n)^2)

Đề bài: BIGPRIME

Để giải được bài này ta có một thuật O(n log(a)^2). Bài này mình nghĩ ra khi chứng minh (n^p + n) % p = 0 ông fermat tìm ra trước nhưng bảo p là số lẻ thì thỏa mãn :V. Nhưng thực tế chỉ có số nguyên tố mới thỏa mãn, thật vậy phương trình trên luôn thỏa mãn với p là số nguyên tố và không thỏa mãn khi p không phải số nguyên tố chứng minh thông qua nhị thức newton (Không có trên mạng đâu =))), n là một số nguyên bất kỳ lớn hơn 1 không chia hết cho p.

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 (ab) 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

// _____ _ _
// / ____| | | (_)
// | (___ ___ _ __ __| | ___ _ __ ______ _ _
// \___ \ / _ \| '_ \ / _ |/ _ \ '_ \ |_ / _ | |
// ____) | (_) | | | | | (_| | __/ |_) | / / (_| | |
// |_____/ \___/|_| |_| \__,_|\___| .__/ /___\__,_|_|
// | |
// |_|
#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 (ab) % 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;
}