编程介的小学生 2018-12-03 14:42 采纳率: 20.5%
浏览 422
已采纳

GCD,一个数字的生成的问题,有点困难,不会

Problem Description
Mr. Frog likes generating numbers! He can generate many numbers from a sequence.

For a given sequence a1,a2,⋯,an Mr. Frog can choose two numbers l and r (1≤l≤r≤n) and calculate the gcd between l-th and r-th number in this sequence g=gcd(al,al+1,⋯,ar). Asan expert in generating numbers, Mr. Frog wants to know how many distinct numbers can be generated by a sequence.

Mr. Frog likes challenges, so there may be many modifications in this sequence. In the i-th modification, Mr. Frog may change ap to vi. After each modification, you are asked to tell how many distinct numbers can be generated by this sequence immediately!

Input
The first line contains only one integer T, which indicates the number of test cases.

For each test case, the first line includes two numbers n, q(1≤n,q≤50000). which indicate the length of sequence and the number of modifications.

The second line contains n numbers:a1,a2,⋯,an.

Then q lines, each line contain two numbers, pi,vi(1≤pi≤n,1≤vi≤1000000).

Test data guarantee that 1<≤ai≤1000000 all the time and the sum of all n and q is less than or equal to 2×105.

Output
For each test case, first output one line "Case #x:", where x is the case number (starting from 1). Then q lines, each line contain only one number, which is the answer to current sequence.

Sample Input
2
3 2
1 2 3
1 3
2 3

3 2
3 3 3
1 1
2 2

Sample Output
Case #1:
3
1
Case #2:
2
3

  • 写回答

1条回答 默认 最新

  • threenewbee 2019-03-28 10:41
    关注
    本回答被题主选为最佳回答 , 对您是否有帮助呢?
    评论

报告相同问题?

悬赏问题

  • ¥15 display:none;样式在嵌套结构中的已设置了display样式的元素上不起作用?
  • ¥15 arduino控制ps2手柄一直报错
  • ¥15 使用rabbitMQ 消息队列作为url源进行多线程爬取时,总有几个url没有处理的问题。
  • ¥15 求chat4.0解答一道线性规划题,用lingo编程运行,第一问要求写出数学模型和lingo语言编程模型,第二问第三问解答就行,我的ddl要到了谁来求了
  • ¥15 Ubuntu在安装序列比对软件STAR时出现报错如何解决
  • ¥50 树莓派安卓APK系统签名
  • ¥65 汇编语言除法溢出问题
  • ¥15 Visual Studio问题
  • ¥20 求一个html代码,有偿
  • ¥100 关于使用MATLAB中copularnd函数的问题