Bài toán 1

Đề bài:

 Cho số tự nhiên a, tìm số tự nhiên n nhỏ nhất sao cho:    $ n^n  \vdots  a, 1 \leq a \leq 10^9 $ 

Ý tưởng: 

Ta phân tích a thành các thừa số nguyên tố.   $ a = \prod_{i=1}^{k} p_{i}^{r_i}$ , với   $ p_i, i = \overline{1..n} $  là các số nguyên tố.

Ta lại có:  $ n^n   \vdots  a \Rightarrow n  =  x\prod_{i=1}^{k} p_{i}$

Vậy bây giờ ta chỉ cần tìm x nhỏ nhất sao cho  $ (xn)^{xn}    \vdots    a $ 

Thuật toán: 

Ta làm theo các bước ở ý tưởng

Ta cần giải quyết bài toán là tính $ a^n   mod  p $  trong thời gian cho phép. 

Ta có:

$ (ab)^n  mod  p = (a^n   mod  p)(b^n  mod  p)   mod   p $

Áp dụng đẳng thức trên và gọi $ f(n) = a^n  mod  p $ 

Ta được:

 $ f(n) = \left\{\begin{matrix}f([\frac{n}{2}])^2  mod  p,   n  \equiv 0  (mod   2) \\  af([\frac{n}{2}])^2  mod  p,  n  \equiv 1   (mod   2) \end{matrix}\right. $ Vậy độ phức tạp của thuật toán chỉ là  $ O(log_{2}n) $

Mã nguồn:

#include <iostream>
using namespace std;
typedef long long ll;

ll power(ll a, ll n, int p) {
if (!n) return 1;
if (n == 1) return a;
ll tmps = power(a, n >> 1, p) % p;
if  (n & 1) return ((tmps*tmps) % p) * a% p;
return tmps * tmps % p;
}

int main() {
int i = 2, A, p;
ll n = 1;
cin >> A; p = A;
while (i*i <= A) {
if (A % i == 0) n *= i;
while (A % i == 0) A /= i;
i++;
}
n = n*A;
i = 1;
while (power(i*n, i*n, p)) i++;
cout << i*n;
system("Pause");
return 0;
}