As we know, Rikka is poor at math. Yuta is worrying about this situation, so he gives Rikka some math tasks to practice. There is one of them:
Alice and Bob are going to play a famous game: Rock-paper-scissors. Both of them don’t like to think a lot, so both of them will use the random strategy: choose rock/paper/scissors in equal probability.
They want to play this game n times, then they will calculate the score s in the following way: if Alice wins a times, Bob wins b times, and in the remaining n−a−bgames they make a tie, the score will be the greatest common divisor of a and b.
Know Yuta wants to know the expected value of s×32n. It is easy to find that the answer must be an integer.
It is too difficult for Rikka. Can you help her?
Note: If one of a,b is 0, we define the greatest common divisor of a and b as a+b.
1836: Rikka with Rock-paper-scissors
时间限制: 20 Sec 内存限制: 128 MB提交: 3 解决: 1
[提交][状态][讨论版][命题人:]
题目描述
输入描述
The first line contains a number t(1≤t≤20), the number of the testcases. There are no more than 2 testcases with n≥104.
For each testcase, the first line contains two numbers n,mo(1≤n≤105,108≤mo≤109)
It is guaranteed that mo is a prime number.
For each testcase, the first line contains two numbers n,mo(1≤n≤105,108≤mo≤109)
It is guaranteed that mo is a prime number.
输出描述
For each testcase, print a single line with a single number -- the answer modulo mo.
样例输入
5
1 998244353
2 998244353
3 998244353
4 998244353
5 998244353样例输出
6
90
972
9720
89910来源
-
Anything about this OnlineJudge, Please Contact Administrator. Click add QQ
OJ system based on HUSTOJ Project , UI based on Twitter Bootstrap
Copyright 2016 ACM算法攻关部
关于网站改版