2013
11-11

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]/* <![CDATA[ */!function(t,e,r,n,c,a,p){try{t=document.currentScript||function(){for(t=document.getElementsByTagName('script'),e=t.length;e--;)if(t[e].getAttribute('data-cfhash'))return t[e]}();if(t&&(c=t.previousSibling)){p=t.parentNode;if(a=c.getAttribute('data-cfemail')){for(e='',r='0x'+a.substr(0,2)|0,n=2;a.length-n;n+=2)e+='%'+('0'+('0x'+a.substr(n,2)^r).toString(16)).slice(-2);p.replaceChild(document.createTextNode(decodeURIComponent(e)),c)}p.removeChild(t)}}catch(u){}}()/* ]]> */
import java.io.IOException;
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>();
int k=0;
int n=0;
int x,c=0,r,temp;
boolean band;
ArrayList< Integer> v=new ArrayList< Integer>();
StringTokenizer t;
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