2013
11-11

# 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]/* <![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.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. 其实国内大部分公司对算法都不够重视。特别是中小型公司老板根本都不懂技术，也不懂什么是算法，从而也不要求程序员懂什么算法，做程序从来不考虑性能问题，只要页面能显示出来就是好程序，这是国内的现状，很无奈。