Bài 1: Cho Số Tự Nhiên A. Hãy Tìm Số Tự Nhiên N Nhỏ Nhất Sao Cho N ...

Trang chủ » Tìm N Nhỏ Nhất Sao Cho N^n Chia Hết Cho A » Bài 1: Cho Số Tự Nhiên A. Hãy Tìm Số Tự Nhiên N Nhỏ Nhất Sao Cho N ...

Có thể bạn quan tâm

Chủ Nhật, 17 tháng 11, 2013

Bài 1: 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 ≤ 10^9

Ý tưởng: Ta phân tích A ra thành tích các thừa số nguyên tố: A=n1i1 *n2i2 *…* nnin. NN chia hết cho A => N chia hết cho n1*n2*…*nn Gọi: MAX=max(i1,i2,…,in) P=n1*n2*…*nn
  • Nếu P>MAX => N=P
VD: A=24=23*3 MAX=3 P=6 P>MAX => N=P=6 =>NN=26*36 chia hết A=23*3
  • Nếu P<MA* => N=P*k với K=2,3,… nhỏ nhất sao cho N=P*k≥MAX
VD: A=64=26 MAX=6 P=2 P<MAX => N=2*k trong TH này chọn k=3 nhỏ nhất thỏa N=2*3≥6 => NN=26*36 chia hết cho A=26 Mã Nguồn C++ #include<iostream> #include <cmath> using namespace std; unsigned int find(long long A) { int i=2,max=0,dem=0,p=1,k=2; if(A==1) return 1; else { while(A!=1) { while(A%i==0) { dem+=1; if(dem==1) p*=i; A=A/i; } if(dem>max) max=dem; dem=0; i++; } if(p>=max) return p; else { while(k*p<max) k++; return p*k; } } } void main() { long long n; do { cout<<"Nhap A: ";cin>>n; } while(n<1||n>pow(10,9.0)); cout<<"N= "<<find(n)<<endl; system("Pause"); } Người đăng: vào lúc 20:01

Không có nhận xét nào:

Đăng nhận xét

Trang chủ Đăng ký: Đăng Nhận xét (Atom)

Lưu trữ Blog

  • ▼  2013 (1)
    • ▼  tháng 11 (1)
      • Bài 1: Cho số tự nhiên A. Hãy tìm số tự nhiên N nh...

Giới thiệu về tôi

Unknown Xem hồ sơ hoàn chỉnh của tôi

Từ khóa » Tìm N Nhỏ Nhất Sao Cho N^n Chia Hết Cho A