Từ 1 tới 1 trên tổng số 1 kết quả

Đề tài: Thuật toán và ý nghĩa của hàm

  1. #1
    Ngày gia nhập
    09 2011
    Nơi ở
    KCN Tiên Sơn , Bắc Ninh
    Bài viết
    1

    Wink Thuật toán và ý nghĩa của hàm

    Mọi người giúp mình với, mình muốn hỏi thuật toán của bài này:

    cho trước 1 dãy số. chọn 2 số A và B bất kì trong dãy và một số nguyên tố X sao cho A chia hết cho X.sau đó xóa A và thay vào đó bởi A/X,xóa B thay vào đó B*X.thực hiện việc này nhiều lần.tìm số lần ít nhất có thể để tìm ước số chung lớn nhất của tất cả các số trong dãy khi biến đổi dãy như vậy.

    mình đã đọc lời giải bài này nhưng có một số hàm mình ko hiểu . các bạn giải thích hộ mình :

    Code:
    #include <cstdio>
    const int MAX=1000000;
    using namespace std;
    int s[MAX+5],n,a[105],A[MAX],c=0;
    void snt(int x) 
    {
    	int t=2;
    	while(t*t<=x) 
        {
    		while(x%t==0) 
            {
    			s[t]++;
    			x=x/t;
    		}
    		t++;
    	}
    	if(x>1) s[x]++;
    }
    int ketqua() 
    {
    	int i,j,r=1;
        c=0;
    	for(i=2;i<=MAX;i++) 
        {
    		s[i]=s[i]/n;
    		for(j=0;j<s[i];j++) r=r*i;
    		if(s[i]>0) A[c++]=i;
    	}
    	return r;
    }
    int sobuoc(int x) 
    {
    	int i,p=0,b,t;
    	for(i=0;i<c;i++) 
        {
    		 b=A[i];
             t=s[b];
    		 while (x%b==0)
             {
                   t--;
                   x=x/b;
             }
    		 if(t>0) p+=t;
    	}
    	return p;
    }
    main() 
    {
    	int i,p=0,r;
    	scanf("%d",&n);
    	for(i=0;i<n;i++) 
        {
    		scanf("%d",&a[i]);
    		snt(a[i]);
    	}
    	r=ketqua();
    	for(i=0;i<n;i++) p+=sobuoc(a[i]);
    	printf("%d %d",r,p);
    	return 0;
    }
    đây là 1 bài trên COCI ngày 12-2-2010 bằng tiếng anh nguyên văn là :

    Mirkos great grandmother Katica is an avid mathematician. She likes to torment Mirko
    with math games. This time she wrote down a sequence of numbers on a piece of
    paper and told Mirko he may do the following:
    • Choose any two numbers in the sequence (let's call them A i B) and a prime
    number X such that A is divisible by X. After that, Mirko erases A and writes
    in its place. In the end he erases B and writes in its place.
    Mirko may perform this operation as many times he wants. His goal is to obtain the
    maximum possible score, because he gets candy from his great grandmother if he does
    so. The score for one sequence is the greatest common divisor of all the numbers
    in the sequence.
    He is not very good at this, and he likes his candy so he has asked you to help him.
    Write a program that will calculate the maximum possible score. Since you are such a nice guy, you should also print the smallest number of times Mirko must perform the operation to obtain the maximum possible score.

    mọi người cứ chém nhiệt tình đi
    Đã được chỉnh sửa lần cuối bởi yeutin : 03-12-2011 lúc 09:58 PM.
    Học dốt C++ nhưng thích học C++

Các đề tài tương tự

  1. Bán công nghệ ổn định mái dốc xây dựng kỹ thuật cao
    Gửi bởi quocquang356 trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 14-09-2012, 11:25 AM
  2. Bán Nhà ở Hoàng Cầu - Thuận tiện Công Việc – Nghỉ Ngơi An Lành
    Gửi bởi tungvnsmart trong diễn đàn Giới thiệu website, sản phẩm của bạn
    Trả lời: 0
    Bài viết cuối: 08-07-2011, 12:05 PM
  3. Lập trình C | Liệt kê các số thuận nghịch có 5 chữ số
    Gửi bởi muadem trong diễn đàn Thắc mắc lập trình C/C++/C++0x
    Trả lời: 8
    Bài viết cuối: 16-01-2010, 05:09 PM
  4. Nghệ thuật cua gái :D
    Gửi bởi neo8x trong diễn đàn Giải trí - Thư giãn
    Trả lời: 10
    Bài viết cuối: 22-03-2009, 08:41 AM

Quyền hạn của bạn

  • Bạn không thể gửi đề tài mới
  • Bạn không thể gửi bài trả lời
  • Bạn không thể gửi các đính kèm
  • Bạn không thể chỉnh sửa bài viết của bạn