首页 > 试题广场 >

数列互质

[编程题]数列互质

热度指数：136 时间限制：C/C++ 6秒，其他语言12秒空间限制：C/C++ 512M，其他语言1024M
算法知识视频讲解

给出一个长度为 n 的数列 { a[1] , a[2] , a[3] , ... , a[n] }，以及 m 组询问 ( l[i] , r[i] , k[i])。
求数列下标区间在 [ l[i] , r[i] ] 中有多少数在该区间中的出现次数与 k[i] 互质（最大公约数为1）。

输入描述:

第一行，两个正整数 n , m (1 ≤ n, m ≤ 50000)。
第二行，n 个正整数 a[i] (1 ≤ a[i] ≤ n)描述这个数列。
接下来 m 行，每行三个正整数 l[i] , r[i] , k[i] (1 ≤ l[i] ≤ r[i] ≤ n, 1 ≤ k[i] ≤ n)，描述一次询问。

输出描述:

输出 m 行，即每次询问的答案。

示例1

输入

10 5
1 1 1 1 1 2 2 2 2 2
4 7 2
4 7 3
4 8 2
4 8 3
3 8 3

输出

算法知识视频讲解

元气の悟空


	#include<stdio.h>
#include<string.h>
int n,m,a[50005],cnt[50005],i,l,r,k,j;
int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
int main(){
    //freopen("input.txt","r",stdin);
    scanf("%d%d",&n,&m);
    for(i=0;i<n;i++) scanf("%d",a+i);
    for(i=0;i<m;i++){
        scanf("%d%d%d",&l,&r,&k);
        memset(cnt,0,sizeof(cnt));
        for(j=l-1;j<=r-1;j++) cnt[a[j]]++;
        int res=0;
        for(j=l-1;j<=r-1;j++) 
            if(cnt[a[j]]) res+=(gcd(cnt[a[j]],k)==1?1:0),cnt[a[j]]=0;
        printf("%d\n",res);
    }
}

编辑于 2017-11-13 20:13:46 回复(0)