首页 > 专题系列 > Java解POJ > POJ 2696 A Mysterious Function [解题报告] Java
2013
11-11

POJ 2696 A Mysterious Function [解题报告] Java

A Mysterious Function

问题描述 :

For any integers p and q with q > 0, define p mod q to be the integer r with 0 <= r <= q −1 such that p−r is divisible by q. For example, we have
    109 mod 10 = 9

    −7 mod 3 = 2

    −56 mod 7 = 0

Let Φ be a function defined recursively as follows.



where a, b, c, d, e, f, g, h are integers with 0 < a, b, c, d, e, f, g, h <= 1000. One can easily see that 0 <= Φ(i) <= 1000 holds for any integer i >= 0. Now for any given integers a, b, c, d, e, f, g, h, i with 0 < a, b, c, d, e, f, g, h, i <= 1000, you are asked to write a program to output

Φ(i). (Hint: a direct recursive implementation of the above recurrence

relation is likely to run forever for large i.)

输入:

The first line contains the number n of test cases. Each of the following n lines contains the sequence a, b, c, d, e, f, g, h, i of integers.

输出:

For each test case, your program has to output the correct value of Φ(i).

样例输入:

3
1 2 3 4 5 6 7 8 9
11 12 13 14 15 16 17 18 19
321 322 323 324 325 326 327 328 329

样例输出:

4
0
90

解题代码:

//* @author: [email protected]
import java.util.Scanner;
public class Main
{
 public static void main(String[] args)
 {
  Scanner in=new Scanner(System.in);
  int k=in.nextInt();
  while((k--)!=0)
  {
    int[] arr=new int[9];
    for(int i=0;i< 9;i++)
    arr[i]=in.nextInt();
    int[] y=new int[arr[8]+1];
    y[0]=arr[0];
    y[1]=arr[1];
    y[2]=arr[2];
    for(int i=3;i<=arr[8];i++)
	 f(y,i,arr);
    System.out.println(y[arr[8]]);
   }
 }


  public static void f(int[] y,int n,int[] arr)
  {
   int u=0;
   if(n%2==1){
     u=arr[3]*y[n-1]+arr[4]*y[n-2]-arr[5]*y[n-3];
     u=(u%arr[6]+arr[6])%arr[6];
    }
    else
    {
	u=arr[5]*y[n-1]-arr[3]*y[n-2]+arr[4]*y[n-3];
	u=(u%arr[7]+arr[7])%arr[7];
     }
  y[n]=u;
 }
}

  1. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术,也不懂什么是算法,从而也不要求程序员懂什么算法,做程序从来不考虑性能问题,只要页面能显示出来就是好程序,这是国内的现状,很无奈。