首页 > ACM题库 > HDU-杭电 > hdu 2248 纷菲幻剑录 之 十年一剑待解决[解题报告]C++
2014
01-04

hdu 2248 纷菲幻剑录 之 十年一剑待解决[解题报告]C++

纷菲幻剑录 之 十年一剑

问题描述 :

黄沙点点扬剑处,流光一瞬已千年……
带着最初的梦想,穿过孤烟大漠,踏进这个繁杂的中原,心中的目标始终不曾改变……
(以上是亦纷菲感人肺腑的吟诗,字字珠玑,句句恳切)
(以下是ZTY描述的中原故事虚构:大意是灭“深犬”-_-||,救pacision)
说时迟,那时快,亦纷菲拿出他的幻剑向深犬刺去,可惜啊可惜~~可惜什么呢? 那么我们先来进m段广告,每段广告又分为s段小广告(因为广告太费时间, 而且试问做题的时候怎么能看广告呢,所以这里就把广告这一段略去了,不知大家意下如何? 如果同意的话那就继续读题)话说当时亦纷菲拿出他的幻剑向深犬刺去, first blood !可惜事情并没有那么简单, 眼看深犬奄奄一息之时,天上下起了甘露,"深犬进化!"深犬大喊, "迭代深犬!!!", 原来深犬汲取日月之精华,天地之灵气, 进化成了无坚不摧,以一敌万的"迭代深犬",亦纷菲知道此时的他已然不敌,于是万般无奈之下他决定暂避锋芒,使出一招"凌波微步",消失在灯火阑珊处,谁料亦纷菲的幻剑竟然留在了迭代深犬那里,又不好意思回去拿,只好求助<英雄哪里出来>,<英雄哪里出来>是一位隐藏人物,据说出没于幽云十六州,由于世俗纷争,是故退隐山林,因为十年前遇上亦纷菲,又因为一饭之恩以幻剑相赠,可惜铸造幻剑需要一把以类铸成的宝剑镶上h(1 <= h <= n)颗壮志凌云石方可铸造成功,于是亦纷菲花了五年写了个类,并且将之铸成宝剑,再去找<英雄哪里出来>,这时<英雄哪里出来>说五年前他说的话中有错别字,是"以泪铸成的宝剑", 而不是"以类铸成的宝剑","挫折,真的是人生要走的路吗?"亦纷菲耳边回荡起这句话,但试问亦纷菲又怎么会轻言放弃, 又是五年不眠不休铸造出了"以泪铸成的宝剑"(所谓“以泪铸成的宝剑”的特殊之处在于它的每一个部分都是一个数字1,共有g个部分,当g == 3,就是111,g == 4 时,就是1111,而且要保证它能够铸成幻剑的必要条件是由g必须为素数,比如3为素数,所以它有机会成为幻剑,但是这仅仅是必要条件),接下来的工作找到h颗壮志凌云石,但是<英雄哪里出来>给了亦纷菲 n(3 <= n <= 20000)颗壮志凌云石,每颗都有颜色,用一个正整数t(0 <= t <= n)来表示,将这些石头排成一排,让你挑出其中连续的h颗,但是壮志凌云石之间有"异元互质"作用,听黑衣人说,如果h颗满足"灵异约束",那么他们之间没有"异元互质",是可以铸成幻剑的,所谓灵异约束就是说任意选择连续h颗,总和sum % n == 0 则称这h颗石头满足灵异约束。

(以下是亦纷菲亲笔)
材料已有还需打造之法,询问<英雄哪里出来>,想要得知打造之法需要回答<英雄哪里出来>的一个问题。题意是 给你2个整数 x,k. (1<=x<6400000 && 0<k<=2^31-1),要你找出 x 的第k大 素因子(如果不存在回答"no")for example x=48, k=6. 48分解的{2,2,2,2,3} 所以1-4大素因子都是2,第5大是3,比5大则没有,
成功铸得幻剑后,挑战深犬。 但深犬也要你回答一道题目方能和接受你的挑战(-_-||汗~~~),题意是这样的,用剑气在悬崖壁上刻出2^n
(1=<n<=20000);

当然这对亦纷菲来说自然是不在话下,轻松解决,于是大战犹如箭在弦上,一触即发!
(待续…)

输入:

现在的亦纷菲已然不是当时的亦纷菲,但是对于曾经的一切一切历历在目,于是他打算模拟一下当时的情景以慰深犬在天之灵,亦纷菲现在要做的工作是:
1.判断一把剑是否有机会成为幻剑
2.找出符合题意的壮志凌云石
3.从<英雄哪里出来>口中得知打造之法
4.回答深犬的问题
首先输入一个字符串Str,该字符串有四种形式:
(1)Swords 然后跟一个整数num,该数字全部由1组成,保证数字长度小于一百;
(2)Stones 然后跟一个整数n(3 <= n <= 20000),接下来一行输入n个数字;
(3)Search 然后跟着2个整数x,k,(1<=x<6400000 && 0<k<=2^31-1);
(4)See 然后跟着1个整数n,(1=<n<=16000);

输出:

现在的亦纷菲已然不是当时的亦纷菲,但是对于曾经的一切一切历历在目,于是他打算模拟一下当时的情景以慰深犬在天之灵,亦纷菲现在要做的工作是:
1.判断一把剑是否有机会成为幻剑
2.找出符合题意的壮志凌云石
3.从<英雄哪里出来>口中得知打造之法
4.回答深犬的问题
首先输入一个字符串Str,该字符串有四种形式:
(1)Swords 然后跟一个整数num,该数字全部由1组成,保证数字长度小于一百;
(2)Stones 然后跟一个整数n(3 <= n <= 20000),接下来一行输入n个数字;
(3)Search 然后跟着2个整数x,k,(1<=x<6400000 && 0<k<=2^31-1);
(4)See 然后跟着1个整数n,(1=<n<=16000);

样例输入:

Swords 11111
Swords 1111
Stones 4
1 3 3 4
Stones 6
1 1 1 1 1 1
Search
3 1
Search
6 2
Search
48 6
See
2
See
20

样例输出:

Yes.
No.
4
1 2 3 4 5 6
3
3
no
4
1048576