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;
}