Thứ Sáu, 15 tháng 11, 2013

Bài toán về thừa số nguyên tố

Đề bài:
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:
Ta phân tích A thành thừa số các số nguyên tố: 
      An1axn2bxn3cx….xnnz  với  n1,n2,n3,..,nlà 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)
{
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