1054 - Efficient Pseudo Code

pseudo codeSometimes it's quite useful to write pseudo codes for problems. Actually you can write the necessary steps to solve a particular problem. In this problem you are given a pseudo code to solve a problem and you have to implement the pseudo code efficiently. Simple! Isn't it? 🙂

{

take two integers n and m

let p = n ^ m (n to the power m)

let sum = summation of all the divisors of p

let result = sum MODULO 1000,000,007

}

Now given n and m you have to find the desired result from the pseudo code. For example if n = 12 and m = 2. Then if we follow the pseudo code, we get

pseudo code

{

take two integers n and m

so, n = 12 and m = 2

let p = n ^ m (n to the power m)

so, p = 144

let sum = summation of all the divisors of p

so, sum = 403, since the divisors of p are 1, 2, 3, 4, 6, 8, 9, 12, 16, 18, 24, 36, 48, 72, 144

let result = sum MODULO 1000,000,007

so, result = 403

}

Input

Input starts with an integer T (≤ 5000), denoting the number of test cases.

Each test case will contain two integers, n (1 ≤ n) and m (0 ≤ m). Each of n and m will be fit into a 32 bit signed integer.

Output

For each case of input you have to print the case number and the result according to the pseudo code.

Sample Input	Output for Sample Input
312 212 136 2	Case 1: 403Case 2: 28Case 3: 3751

 

题目类型：素因子分解+逆元+整数快速幂取模

算法分析：首先使用Euler筛将素数预打表，然后从小到大判断每个素数在a中出现的指数值，然后带入约数和公式边模边求解，这里使用了一个求逆元非常好的公式：a / b mod (p) = a mod (mb) / m，由于指数比较大，所以要使用整数快速幂来加速运算，注意在判断条件primelist[i] * primelist[i] <= a时primelist[i]*primelist[i]相乘的结果应该强制转换成long long，否则会RE

 

« 上一篇：lightoj1045

lightoj1056：下一篇 »