PSTR - Number of Prime Strings
A string is called a "prime string" if it can't be written as concatenation of more than one same strings. For example, the following strings are not prime strings: AAA, ABABAB, CFGFGCFGFG, while CFGFGC, ABABA are prime strings.
Calculate the number of prime string of length N (1<=N<=1000000), and only contains first K (1<=K<=26) letters from English alphabet. Note that some of these K letters need not appear in that string.
Multiple test cases. The number of them (about 10000) is given in the very first line.
Each test case contains one line with two integers - K and N, seperated by a single space.
For each test case, output the required number modulo 1000000007 in a single line.
The prime strings of length 3 which only contain character 'A' and 'B' are: AAB,ABA,ABB,BAA,BAB,BBA.
1 <= N <= 1000000 1 <= K <= 26
Total number of test cases is around 10000.
The time limit is not strict. Just need some observation to clear it.
(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†):
@YangYue: I'm sorry, but I think time limit is not too strict, this problem can be solved under 0.1s without any large precomputation... time limit is about 11 times slower than optimal solution...Last edit: 2012-12-13 09:18:07