首页 > 专题系列 > Java解POJ > POJ 3406 Last digit [解题报告] Java
2013
11-12

POJ 3406 Last digit [解题报告] Java

Last digit

问题描述 :

Determine the last nonzero digit in value of expression

.

输入:

The input contains a single line with n and m separated by one or several spaces; n, m are natural numbers from 1 to 1000000, nm.

输出:

The output contains a single line with the last nonzero digit.

样例输入:

4 2

样例输出:

6

解题代码:

//* @author: [email protected]
import java.util.Scanner;
public class Main
{
 public static void main(String[] args)
 {
   Scanner in=new Scanner(System.in);
   int[] b2=new int[]{6,2,4,8};
   int[] b3=new int[]{1,3,9,7};
   int[] b7=new int[]{1,7,9,3};
   int[] b9=new int[]{1,9,1,9};
   int n=in.nextInt();
   int m=in.nextInt();
   int w=n-m;
   int e,a2=0,a3=0,a5=0,a7=0,a9=0;
   e=n;while((e=e/2)!=0) a2+=e;
   e=m;while((e=e/2)!=0) a2-=e;
   e=w;while((e=e/2)!=0) a2-=e;
   e=n;while((e=e/5)!=0) a5+=e;
   e=m;while((e=e/5)!=0) a5-=e;
   e=w;while((e=e/5)!=0) a5-=e;
   a3=f(n,3)-f(m,3)-f(w,3);
   a7=f(n,7)-f(m,7)-f(w,7);
   a9=f(n,9)-f(m,9)-f(w,9);
   int ans=1;
   if(a5>a2) System.out.println(5);
   else{
	a2-=a5;
	if(a2!=0){
         a2=a2%4;
	  ans*=b2[a2];
	  ans=ans%10;
	}
	ans*=b3[(a3%4+4)%4];
	ans=ans%10;
	ans*=b7[(a7%4+4)%4];
	ans=ans%10;
	ans*=b9[(a9%4+4)%4];
	ans=ans%10;
	System.out.println(ans);
    }
  }

  public static int f(int n,int a)
  {
	if(n==0) return 0;
	else return f(n/2,a)+g(n,a);
   }

  public static int g(int n,int a)
  {
	if(n==0)return 0;
	else if(n%10< a)return n/10+g(n/5,a);
	else return n/10+1+g(n/5,a);
  }
}

  1. 第一题是不是可以这样想,生了n孩子的家庭等价于n个家庭各生了一个1个孩子,这样最后男女的比例还是1:1

  2. 有限自动机在ACM中是必须掌握的算法,实际上在面试当中几乎不可能让你单独的去实现这个算法,如果有题目要用到有限自动机来降低时间复杂度,那么这种面试题应该属于很难的级别了。

  3. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮

  4. 约瑟夫也用说这么长……很成熟的一个问题了,分治的方法解起来o(n)就可以了,有兴趣可以看看具体数学的第一章,关于约瑟夫问题推导出了一系列的结论,很漂亮