首页 > 其他 > 详细

HDU 多校1.4

时间：2017-07-25 13:13:13      阅读：336      评论：0      收藏：0      [点我收藏+]

Division Game

Time Limit: 10000/5000 MS (Java/Others)    Memory Limit: 131072/131072 K (Java/Others)
Total Submission(s): 0    Accepted Submission(s): 0


Problem Description
There are k技术分享 piles of stones in a circle, numbered from 0技术分享 to k−1技术分享 , where the number of the stones in each pile is n技术分享 initially. You can do some round operations, where the initial round is numbered as the 1技术分享 -st round.

The operation of the i技术分享 -th round is to modify the pile of stones numbered (i−1)modk技术分享 . In each round, you should remove from this pile some stones (at least one stone), satisfying that the number of stones in this pile before this operation is a multiple of the number of stones in this pile after operation, which means that you ought to remain at least one stone in this pile.

The game is ended if there exists at least one pile containing only one stone. Given two positive integers n技术分享 and k技术分享 , your task is to calculate for each pile the number of the possible operation plans that it is the last operated pile before the game is ended.

The integer n技术分享 may be very large, so the prime-factor decomposition of n技术分享 will be given, in other words, if n=∏技术分享m技术分享i=1技术分享p技术分享e技术分享i技术分享技术分享i技术分享技术分享 , then the integers m技术分享 and (p技术分享i技术分享,e技术分享i技术分享)技术分享 (1≤i≤m)技术分享 will be given, but the integer n技术分享 will not.

The answer may be very large, so you only need to give the value of the answer modulo 985661441技术分享 .
 

 

Input
The input contains multiple test cases.

For each test case:

The first line contains two positive integers m技术分享 and k技术分享 , satisfying that 1≤m,k≤10技术分享 .

In next m技术分享 lines, the i技术分享 -th line contains two positive integers p技术分享i技术分享技术分享 and e技术分享i技术分享技术分享 , satisfying that 2≤p技术分享i技术分享≤10技术分享9技术分享,技术分享 e技术分享i技术分享≥1,技术分享 ∑技术分享m技术分享i=1技术分享e技术分享i技术分享≤10技术分享5技术分享技术分享 .

It is guaranteed that p技术分享1技术分享,p技术分享2技术分享,?,p技术分享m技术分享技术分享 are distinct.

About 200技术分享 test cases in total, where no more than 5技术分享 cases satisfy ∑技术分享m技术分享i=1技术分享e技术分享i技术分享≥10技术分享4技术分享技术分享 .
 

 

Output
For each test case, output "Case #x技术分享 : y技术分享0技术分享技术分享 y技术分享1技术分享技术分享 ?技术分享 y技术分享k−1技术分享技术分享 " in one line (without quotes), where x技术分享 indicates the case number starting from 1技术分享 and y技术分享i技术分享技术分享 (0≤i<k)技术分享 denotes the number of the possible operation plans modulo 985661441技术分享 for the pile numbered i技术分享 of corresponding case.
 

 

Sample Input
1 1 2 2 2 1 3 1 5 1 1 2 2 3 2 2 2 4 5 4
 

 

Sample Output
Case #1: 2 Case #2: 3 Case #3: 6 4 Case #4: 1499980 1281085

HDU 多校1.4

原文：http://www.cnblogs.com/Roni-i/p/7233427.html
踩
(0)
赞
(0)
   
举报
评论 一句话评论（0）
分享档案
更多>
2021年09月23日 (328)
2021年09月24日 (313)
2021年09月17日 (191)
2021年09月15日 (369)
2021年09月16日 (411)
2021年09月13日 (439)
2021年09月11日 (398)
2021年09月12日 (393)
2021年09月10日 (160)
2021年09月08日 (222)
最新文章
更多>
教程昨日排行
更多>
友情链接
汇智网   PHP教程   插件网  
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣，分享程序人生！