Cho số tự nhiên A. Hãy tìm số tự nhiên N nhỏ nhất sao cho N lũy thừa N (nhân N cho chính nó N lần) chia hết cho A. Hãy viết chương trình tìm số N đó và xuất ra màn hình. Trong đó A có giá trị: 1 ≤ A ≤ 109
Bài giải:
Bài giải:
Ta phân tích A thành thừa số các số nguyên tố:
A = n1axn2bxn3cx….xnnz với n1,n2,n3,..,nn là các số nguyên tố.
Ta thấy rằng: NN chia hết cho A khi NN chia hết cho n1axn2bxn3cx….xnnz
Hay NN cũng chia hết cho n1xn2xn3x….xnn
Khi đó NN = Kxn1xn2xn3x….xnn
Vậy N nhỏ nhất khi K nhỏ nhất.
Từ nhận xét trên ta có thể dễ dàng đi tìm K nhỏ nhất thỏa điều kiện:
Kxn1xn2xn3x….xnn mod A = 0
thay vì tìm N sao cho: NN mod A = 0.
Solution tham khảo:
#include<iostream>
#include<algorithm>
typedef long long ll;
long a,s=1;
using namespace std;
int solve(int n)
{
#include<algorithm>
typedef long long ll;
long a,s=1;
using namespace std;
int solve(int n)
{
int i=2;
while (i<=sqrt(1.0*n)) {
if (n%i==0) {
s*=i;
while (n%i==0)
n/=i;
}
i++;
}
if (n>1)
s*=n;
return 0;
}
long long power(long i,long n)
{
if (n==1)
return i;
long long x=power(i,n/2);
x=((x%a)*(x%a))%a;
if (n%2!=0) x=(x*i)%a;
return x;
}
int main()
{
cout<<"Nhap a: ";
cin>>a;
solve(a);
int i=0;
while (power(++i*s,i*s)%a!=0);
cout<<"N = "<<i*s;
return 0;
}
Không có nhận xét nào:
Đăng nhận xét