问题 4401 --2010-网络赛I-穷举先生

4401: 2010-网络赛I-穷举先生

时间限制: 2 Sec  内存限制: 256 MB
提交: 0  解决: 0
[提交][状态][讨论版][命题人:]

题目描述

穷举先先的算法设计很不好。有一次他被要求解决一个问题。他想了好几天,终于想出了下面的算法:

任何傻瓜都知道,这样的代码简直不可思议,Funny函数将被调用非常非常多次。穷举先生想知道Funny函数将被调用的次数,但他懒得去做。

现在的任务是计算Funny函数将被调用多少次,对于给定的a,b和n。因为答案可能太大,所以把答案模P再输出。

输入

有多个测试案例。输入的第一行包含一个整数t,表示测试的个数。

对于每一个测试案例,有四个整数a,b,P,n在每同一行上,P不一定是素数。

输入的数据保证1≤n≤1000000000, 1≤P≤1000000, 0≤a, b<1000000.

输出

一行输出一个答案

样例输入

3<br/>3 5 7 9<br/>2 3 5 7<br/>11 13 17 19

样例输出

4<br/>2<br/>7

提示

图片中用的是伪代码


上面代码翻译为C语言大概是


int a, b, n;


void funny()

{


}


void find(int n, void (*func)())

{

 int i;

 if (1 == n)

 {

  for(i = 0; i < a; ++i)

  {

   func();

  }

 }

 else if (2 == n)

 {

  for(i = 0; i < b; ++i)

  {

   func();

  }

 }

 else find(n - 1, (void (*)())find);  //上面的原来那句C语言似乎没有正面方法来实现

}


int main()

{

 a = 2, b = 2, n = 2; //这几个值是给定的,这里写2只是示例 

 find(n ,funny);

 return 0;

}

来源

[提交][状态]