首页 > 数据结构 > Hash表 > POJ 2649 Factovisors [解题报告] Java
2013
11-11

POJ 2649 Factovisors [解题报告] Java

Factovisors

问题描述 :

The factorial function, n! is defined thus for n a non-negative integer:
   0! = 1

n! = n * (n-1)! (n > 0)

We say that a divides b if there exists an integer k such that

   k*a = b

输入:

The input to your program consists of several lines, each containing two non-negative integers, n and m, both less than 2^31.

输出:

For each input line, output a line stating whether or not m divides n!, in the format shown below.

样例输入:

6 9
6 27
20 10000
20 100000
1000 1009

样例输出:

9 divides 6!
27 does not divide 6!
10000 divides 20!
100000 does not divide 20!
1009 does not divide 1000!

解题代码:

//* @author  [email protected]
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.ArrayList;
import java.util.Hashtable;
import java.util.StringTokenizer;
public class Main {
    public static void main(String[] args) throws IOException {
        Hashtable< Integer,Integer> table=new Hashtable< Integer,Integer>();
        Hashtable< Integer,Integer> table2=new Hashtable< Integer,Integer>();
               BufferedReader stdin=new BufferedReader(new InputStreamReader(System.in));
        int k=0;
        int n=0;
        int x,c=0,r,temp;
        boolean band;
        ArrayList< Integer> v=new ArrayList< Integer>();
        StringTokenizer t;
       while(stdin.ready()){
           t=new StringTokenizer(stdin.readLine());
            n=new Integer(t.nextToken());
            k=new Integer(t.nextToken());
            table.clear();
            table2.clear();
            v.clear();
            band=true;
            x=k;
            if(x!=0)
            {while(x%2==0){
                x/=2;table.put(2, table.get(2)==null?1:table.get(2)+1);
            }
            c=3;
            while(c<=(Math.sqrt((double)x)+1)){
                if(x%c==0){
                    x/=c;
                    table.put(c, table.get(c)==null?1:table.get(c)+1);
                } else c+=2;
            }
            if(x>1)table.put(x, table.get(x)==null?1:table.get(x)+1);
            }
            
            band=true;
            v=new ArrayList(table.keySet());
            if(k!=0&&n!=0&&k>n)
            for(int i=0;i< v.size();i++){
                c=table.get(v.get(i));

                x=0;
                r=0;
                while(x< c){
                    r++;
                    temp=r*v.get(i);
                    if(temp>n){
                        band=false;
                        break;
                    }
                    if(table2.get(temp)==null){
                        table2.put(temp,temp);
                    }
                    while(table2.get(temp)%v.get(i)==0){
                        table2.put(temp, table2.get(temp)/v.get(i));
                        x++;
                        if(x==c)break;
                    }
                }
                if(!band) break;
            }
            if(n==0&&k!=1) band=false;           
            if(band&&k!=0)System.out.println(k+" divides "+n+"!");
            else System.out.println(k+" does not divide "+n+"!");
        }
    }
}

  1. 这道题这里的解法最坏情况似乎应该是指数的。回溯的时候
    O(n) = O(n-1) + O(n-2) + ….
    O(n-1) = O(n-2) + O(n-3)+ …
    O(n) – O(n-1) = O(n-1)
    O(n) = 2O(n-1)

  2. #!/usr/bin/env python
    def cou(n):
    arr =
    i = 1
    while(i<n):
    arr.append(arr[i-1]+selfcount(i))
    i+=1
    return arr[n-1]

    def selfcount(n):
    count = 0
    while(n):
    if n%10 == 1:
    count += 1
    n /= 10
    return count