Một vài bài toán đơn giản.

Cho số tự nhiên A, thỏa $1 \le A \le {10^9}$.
Yêu cầu: tìm số tự nhiên N nhỏ nhất thỏa ${N^N} \vdots A $.



Giải quyết bài toán
$A = {a_1}^{{x_1}}*{a_2}^{{x_2}}*{a_3}^{{x_3}}...*{a_m}^{{x_m}} $
(với $ {a_1}, {a_2}, ..., {a_m}$ là các số nguyên tố)
Gọi $T = {a_1}*{a_2}*{a_3}*...*{a_m}$
Khi đó bài toán của ta đưa về:
 Tìm  số X nhỏ nhất thỏa ${(T*X)^{T*X}} \vdots N$
Ta xét thấy: Max(${x_{_1}},{x_2},...,{x_m}$) $ \le $ $\left[ {{{\log }_2}N} \right] \le \left[ {{{\log }_2}{{10}^9}} \right] = 29$
Từ đó ta rút ra, với T > 29 thì đó hiển nhiên là kết quả của bài toán. Ngược lại ta vét T từ 1 tới khi tìm được kết quả thỏa mãn yêu cầu. Dựa vào chứng minh trên, ta dễ dàng suy ra được T sẽ không bao giờ vượt quá 29.
Vấn đề còn lại là việc tìm Q thỏa $T*X \equiv Q(\bmod N)$
Mọi người có thể tham khảo tài liệu và cách tính lũy thừa nhanh.

Source code

#include <stdio.h>

using namespace std;

typedef long long int64;
int n, k = 1;

int64 pow(int64 x, int64 y)
{
      if (y == 0)
          return 1;
      int64 Ret = pow(x, y/2);
      Ret = Ret * Ret % n;
      if (y & 1)
          Ret = Ret * x % n;
      return Ret;
}



int main()
{

    scanf("%d", &n);

    int temp = n;
    for(int i = 2; i * i <= temp; ++i)
        if (temp % i == 0)
        {
            k *= i;
            while (temp % i == 0) temp /= i;
        }
    k *= temp;

    int64 ans = k;
    while (pow(ans, ans)) ans += k;

    printf("%lld", ans);
    return 0;
}