day2题目项链保护出题人城市.pdfVIP

项链 （necklace） 题目描述： 项链是 的装饰品之一，是最早出现的首饰。项链除了具有装饰功能之外，有些项 链还具有特殊显示作用，如天主 的 链和 徒的念珠。 从古至今人们为了美化 本身，也美 化环境，制造了各种不同风格，不同特点、不 同式样的项链，满足了不同肤色、不同民族、 不同审美观的人的审美需要。就材料而论，首 饰市场上的项链有黄金、白银、珠宝等几种。 珍珠项链为珍珠制成的饰品，即将珍珠 钻孔后用线串在一起，佩戴于项间。天然珍珠 项链具有一定的护养作用。 最近，铭铭迷恋上了一种项链。与其他珍珠项链基本上相同，不过这种项链的珠子却与 众不同，是正三菱柱的泰山石雕刻而成的。三菱柱的侧面是正方形构成的，上面刻有数字。能够让 铭铭满意的项链必须满足下面的条件： 1：这串项链由n 颗珠子构成的。 2：每一个珠子上面的数字 x,必须满足 0x=a，且珠子上面的数字的最大公约数要恰 好为 1。两个珠子被认为是相同的，当且仅当他们经过旋转，或者翻转后能够变成一样的。 3：相邻的两个珠子必须不同。 4：两串项链如果能够经过旋转变成一样的，那么这两串项链就是相同的！ 铭铭很好奇如果给定 n 和a，能够找到多少不同串项链。由于答案可能很大，所以对输 出的答案 mod 。 数据输入： 数据由多组数据构成： 第一行给定一个 T=10，代表由 T 组数据。 接下来 T 行，每行两个数n 和 a。 数据输出： 对于每组数据输出有多少不同的串。 样例输入： 1 2 2 样例输出： 3 数据范围： 对于 10%的数据：所有的 n=10，a=10，T=10； 对于 20%的数据：所有的 n=1000，a=100，T=10； 对于 40%的数据：所有的 n=109 ，a=100，T=10； 6 5 对于 60%的数据：所有的 n=10 ，a=10 ，T=10； 9 5 对于 80%的数据：所有的 n=10 ，a=10 ，T=10； 14 7 对于 100%的数据：所有的 n=10 ，a=10 ，T=10； 样例解释：由三种珠子：[1,1,1],[1,1,2],[1,2,2].组成的串有：[1,2],[1,3],[2,3]。 保护出题人 （defend） 题目描述： 出题人铭铭认为给 S 2012 出题太可怕了，因为总要被 ，于是他又给 S 2013 出题 了。 参加 S 2012 的小朋友们释放出大量的僵尸，企图 铭铭的家。而你作为 S 2013的 参赛者，你需要保护出题人铭铭。 僵尸从唯一一条笔直道路接近， 需要在铭铭的房门前放置植物 僵尸，避免僵尸 碰到房子。第一关，一只血量为 a x 1 点的僵尸从距离房子 1 米处匀速接近，