编程介的小学生 2019-08-24 21:55 采纳率: 20.5%
浏览 178

Rabbit Kingdom用的C语言的程序代码

Problem Description
  Long long ago, there was an ancient rabbit kingdom in the forest. Every rabbit in this kingdom was not cute but totally pugnacious, so the kingdom was in chaos in season and out of season.
  n rabbits were numbered form 1 to n. All rabbits' weight is an integer. For some unknown reason, two rabbits would fight each other if and only if their weight is NOT co-prime.
  Now the king had arranged the n rabbits in a line ordered by their numbers. The king planned to send some rabbits into prison. He wanted to know that, if he sent all rabbits between the i-th one and the j-th one(including the i-th one and the j-th one) into prison, how many rabbits in the prison would not fight with others.
  Please note that a rabbit would not fight with himself.

Input
  The input consists of several test cases.
  The first line of each test case contains two integer n, m, indicating the number of rabbits and the queries.
  The following line contains n integers, and the i-th integer Wi indicates the weight of the i-th rabbit.
  Then m lines follow. Each line represents a query. It contains two integers L and R, meaning the king wanted to ask about the situation that if he sent all rabbits from the L-th one to the R-th one into prison.
  (1 <= n, m, Wi <= 200000, 1 <= L <= R <= n)
  The input ends with n = 0 and m = 0.

Output
  For every query, output one line indicating the answer.

Sample Input
3 2
2 1 4
1 2
1 3
6 4
3 6 1 2 5 3
1 3
4 6
4 4
2 6
0 0

Sample Output
2
1
1
3
1
2

  • 写回答

0条回答 默认 最新

    报告相同问题?

    悬赏问题

    • ¥50 树莓派安卓APK系统签名
    • ¥15 maple软件,用solve求反函数出现rootof,怎么办?
    • ¥65 汇编语言除法溢出问题
    • ¥15 Visual Studio问题
    • ¥20 求一个html代码,有偿
    • ¥100 关于使用MATLAB中copularnd函数的问题
    • ¥20 在虚拟机的pycharm上
    • ¥15 jupyterthemes 设置完毕后没有效果
    • ¥15 matlab图像高斯低通滤波
    • ¥15 针对曲面部件的制孔路径规划,大家有什么思路吗