精华内容
下载资源
问答
  • 一行包含两正整数N、M,分别表示查询的范围和查询的个数。 接下来M行每行包含一不小于1且不大于N的整数,即询问该数是否为质数。 输出格式: 输出包含M行,每行为Yes或No,即依次为每一询问的结果。 ...

    P3383 【模板】线性筛素数

    题目描述

    如题,给定一个范围N,你需要处理M个某数字是否为质数的询问(每个数字均在范围1-N内)

    输入输出格式

    输入格式:

     

    第一行包含两个正整数N、M,分别表示查询的范围和查询的个数。

    接下来M行每行包含一个不小于1且不大于N的整数,即询问该数是否为质数。

     

    输出格式:

     

    输出包含M行,每行为Yes或No,即依次为每一个询问的结果。

     

    输入输出样例

    输入样例#1: 复制
    100 5
    2
    3
    4
    91
    97
    输出样例#1: 复制
    Yes
    Yes
    No
    No
    Yes

    说明

    时空限制:500ms 128M

    数据规模:

    对于30%的数据:N<=10000,M<=10000

    对于100%的数据:N<=10000000,M<=100000

    样例说明:

    N=100,说明接下来的询问数均不大于100且不小于1。

    所以2、3、97为质数,4、91非质数。

    故依次输出Yes、Yes、No、No、Yes。

     

     

     

    题意很好理解,贴一下板子而已。

    代码:

     1 //线性筛法筛素数(欧拉筛法)
     2 #include<iostream>
     3 #include<cstdio>
     4 #include<cstring>
     5 #include<algorithm>
     6 #include<bitset>
     7 #include<cassert>
     8 #include<cctype>
     9 #include<cmath>
    10 #include<cstdlib>
    11 #include<ctime>
    12 #include<deque>
    13 #include<iomanip>
    14 #include<list>
    15 #include<map>
    16 #include<queue>
    17 #include<set>
    18 #include<stack>
    19 #include<vector>
    20 using namespace std;
    21 typedef long long ll;
    22 
    23 const double PI=acos(-1.0);
    24 const double eps=1e-6;
    25 const ll mod=1e9+7;
    26 const int inf=0x3f3f3f3f;
    27 const int maxn=2e7+10;
    28 const int maxm=100+10;
    29 #define ios ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    30 
    31 bitset<maxn> is_prime;
    32 int p[maxn],h=0;
    33 
    34 void Prime(int n)
    35 {
    36     is_prime[0]=1;
    37     is_prime[1]=1;
    38     for(int i=2;i<=n;++i){
    39         if(is_prime[i]==0)
    40             p[++h]=i;
    41         for(int j=1;j<=h&&p[j]*i<=n;++j){
    42             is_prime[i*p[j]]=1;
    43             if(i%p[j]==0)
    44                 break;
    45         }
    46     }
    47 }
    48 
    49 int main()
    50 {
    51     int n,m;
    52     scanf("%d%d",&n,&m);
    53     Prime(n);
    54     for(int i=1;i<=m;i++){
    55         int x;
    56         scanf("%d",&x);
    57         if(is_prime[x])
    58             printf("No\n");
    59         else
    60             printf("Yes\n");
    61     }
    62     return 0;
    63 }

     

     

    溜了。。。

     

    转载于:https://www.cnblogs.com/ZERO-/p/9648402.html

    展开全文
  • Description 给出三个质数,求这素因子只有这三...输出素因子只有这三个质数第n大的数 Sample Input 7 13 19 100 Sample Output 26590291 Solution 这个集合是通过集合里的每一个数 ×a,×b,×c来扩展的,

    Description
    给出三个质数,求这素因子只有这三个质数的数中第k大的
    Input
    输入包括四个整数,前三个为三个质数a,b,c,第四个为查询数n
    Output
    输出素因子只有这三个质数中第n大的数
    Sample Input
    7 13 19 100
    Sample Output
    26590291
    Solution
    这个集合是通过集合里的每一个数 ×a,×b,×c来扩展的,要想从小到大,从ugly[1]开始扩展时,由于×a,×b,×c大小不同,所以ugly[]的下一个元素是这三个数的最小值。所以到下次时,a是在乘以新的元素,而b,c还在乘原来的元素,但这三个数比较后最小的继续添加进集合里。由于有了这样的延迟作用,我们可以设置三个指针pa,pb,pc分别指向a,b,c待乘的数。
    要记得处理重复的数,在每扩展一个元素时,判断该数是否能通过其他数来乘得,是的话就右移p
    Code

    #include<iostream>
    #include<algorithm> 
    using namespace std;
    long long num[100000],a,b,c,pa,pb,pc,n;
    int main()
    {
        while(cin>>a>>b>>c>>n)
        {
            num[0]=1;
            pa=pb=pc=0;
            for (int i=1;i<=n;i++)
            {
                num[i]=min(num[pa]*a,min(num[pb]*b,num[pc]*c));
                if(num[i]==num[pa]*a) 
                    pa++;
                if(num[i]==num[pb]*b) 
                    pb++;
                if(num[i]==num[pc]*c) 
                    pc++;
            }
            cout<<num[n]<<endl;
        }
        return 0;
    }
    展开全文
  • 大于10万的个质数,1e5+3; 1.原子操作 1.1.插入 1.1.1.开放寻址法 h[find(x)]=x; 1.1.2.拉链法 void insert(int x) { int k=(x%N+N)%N; e[idx]=x; ne[idx]=h[k]; h[k]=idx++; } 1.2.查询 1.

    哈希

    mod的数一般取一个质数

    离2的整数次幂尽量远

    大于10万的第一个质数,1e5+3;

    1.原子操作

    1.1.插入

    1.1.1.开放寻址法

    h[find(x)]=x;
    

    1.1.2.拉链法

    void insert(int x)
    {
      int k=(x%N+N)%N;
      e[idx]=x;
      ne[idx]=h[k];
      h[k]=idx++;
    }
    

    1.2.查询

    1.2.1.开放寻址法

    void find(int x){
      int t = (x%N+N)%N;
      
      while(h[t]!=null&&h[t]!=x)
      {
        t++;
        if(t==N) t=0;
      }
      return t;
    }
    

    1.2.3.拉链法

    bool find(int x)
    {
      int k = (x%N+N)%N;
      for(int i=h[k];i!=-1;i=ne[i])
        if(e[i]==x)
          return true;
      return false;
    }
    

    2.字符串哈希

    P一般取131

    首先核心在于,将一段字符串映射为一个数

    abcde注意字符串是从左往右看的,但是从右往左依次是高位。

    那么求de这个字符串表示时候,l=4,r=5

    h[r]=h[5]h[r]=h[5],代表abcdeabcde代表aq5+bq4+cq3+dq2+eq1a*q^5+b*q^4+c*q^3+d*q^2+e*q^1

    h[l1]=h[3]h[l-1]=h[3]代表abcabc代表aq3+bq2+cq1a*q^3+b*q^2+c*q^1

    下面是一个小技巧,使用ULL,相当于队2642^{64}取模

    ULL get(int l,int r)
    {
      return h[r]-h[l-1]*q[r-l+1];
    }
    
    ULL h[N],p[N];
    
    int main(){
      scanf("%d%d",&n,&m);
      scanf("%s",str+1);
      p[0]=1;
      
      for(int i=1;i<=n;i++);
      {
        h[i]=h[i-1]*P+str[i];
        p[i]=p[i-1]*P;
      }
      while(m--)
      {
        int l1,r1,l2,r2;
        scanf("%d%d%d%d",&l1,&r1,&l2,&r2);
        if(get(l1,r1)==get(l2,r2)) puts("Yes");
        else puts("No");
      }
      return 0;
    }
    
    展开全文
  • 洛谷 模板题 P3383 ...一行包含两正整数N、M,分别表示查询的范围和查询的个数。 接下来M行每行包含一不小于1且不大于N的整数,即询问该数是否为质数。 输出格式: 输出包含M行,每行为Yes或N

    洛谷  模板题 P3383

     

    题目描述

     

    如题,给定一个范围N,你需要处理M个某数字是否为质数的询问(每个数字均在范围1-N内)

    输入输出格式

    输入格式:

     

     

     

    第一行包含两个正整数N、M,分别表示查询的范围和查询的个数。

    接下来M行每行包含一个不小于1且不大于N的整数,即询问该数是否为质数。

     

    输出格式:

     

     

     

    输出包含M行,每行为Yes或No,即依次为每一个询问的结果。

     

    输入输出样例

    输入样例#1: 
    100 5
    2
    3
    4
    91
    97
    输出样例#1: 
    Yes
    Yes
    No
    No
    Yes

     

     

     

     

     

     

     

     

     

     

     

     

     

     

    #include<iostream>

    using namespace std;

    int tot=0;//素数的个数

    int p[10000001];//对不是素数的数进行标记

    int c[10000001];//c[i]表示第i个素数

    int n,m;

    int sushu(int x)//在1-x中 把合数 标记
    {
        for(int i=2;i<=x;i++)//从2开始  
        {
            if(p[i]!=1)c[tot++]=i;//如果循环到i的时候 i没被标记 那么i就是 一个素数
            for(int j=0;j<tot;j++)
            {

                if(i*c[j]>x)break;  //不用对超出范围的数进行判断

       p[i*c[j]]=1;//让i与之前查询到的素数相乘得到的数一定是合数


                if(i%c[j]==0)break;//如果i是 之前查询到的素数的倍数 就可以跳出来换下一个i

            }
        }
    }
    int main()
    {
        cin>>n>>m;//1-n的范围 m次询问
        sushu(n);
        for(int i=1;i<=m;i++)
        {
            cin>>n;
            if(n==1)//1既不是素数 也不是合数
            {
                cout<<"No"<<endl;
                continue;
            }
            if(p[n])
            {
                cout<<"No"<<endl;
            }
            else cout<<"Yes"<<endl;
        }
    }

    展开全文
  • 线性筛素数

    2019-04-10 21:40:17
    K : 线性筛素数 Time Limit:5 Sec Memory Limit:128 MiB ...一行包含两正整数N、M,分别表示查询的范围和查询的个数。接下来M行每行包含一不小于1且不大于N的整数,即询问该数是否为质数。 数据规模...
  • 一行包含两正整数N、M,分别表示查询的范围和查询的个数。 接下来M行每行包含一不小于1且不大于N的整数,即询问该数是否为质数。 输出格式: 输出包含M行,每行为Yes或No,即依次为每一询问的结果...
  • 一行包含两正整数N、M,分别表示查询的范围和查询的个数。 接下来M行每行包含一不小于1且不大于N的整数,即询问概数是否为质数。 输出格式: 输出包含M行,每行为Yes或No,即依次为每一询问的结果。...
  • 一行包含两正整数N、M,分别表示查询的范围和查询的个数。 接下来M行每行包含一不小于1且不大于N的整数,即询问该数是否为质数。 输出格式: 输出包含M行,每行为Yes或No,即依次为每一询问的结果。 ...
  • 一行包含两正整数N、M,分别表示查询的范围和查询的个数。 接下来M行每行包含一不小于1且不大于N的整数,即询问该数是否为质数。 输出格式: 输出包含M行,每行为Yes或No,即依次为每一询问的结果...
  • 一行包含两正整数N、M,分别表示查询的范围和查询的个数。 接下来M行每行包含一不小于1且不大于N的整数,即询问该数是否为质数。 输出格式: 输出包含M行,每行为Yes或No,即依次为每一询问的结果。 ...
  • 题目描述 如题,给定一范围N,你需要处理M某数字是否...一行包含两正整数N、M,分别表示查询的范围和查询的个数。 接下来M行每行包含一不小于1且不大于N的整数,即询问概数是否为质数。 输出格式:...
  • 每日题解

    2019-05-23 20:28:00
    一行包含两正整数N、M,分别表示查询的范围和查询的个数。 接下来M行每行包含一不小于1且不大于N的整数,即询问该数是否为质数。 输出格式: 输出包含M行,每行为Yes或No,即依次为每一询问的结果。 埃氏筛...
  • 线性筛板子

    2019-08-07 11:13:00
    一行包含两正整数N、M,分别表示查询的范围和查询的个数。 接下来M行每行包含一不小于1且不大于N的整数,即询问该数是否为质数。 输出格式 输出包含M行,每行为Yes或No,即依次为每一询问的结果。 ...
  • 一行包含两正整数N、M,分别表示查询的范围和查询的个数。 接下来M行每行包含一不小于1且不大于N的整数,即询问该数是否为质数。 输出格式: 输出包含M行,每行为Yes或No,即依次为每一询问的结果。 ...
  • 素数筛

    2018-01-05 16:47:00
    一行包含两正整数N、M,分别表示查询的范围和查询的个数。 接下来M行每行包含一不小于1且不大于N的整数,即询问该数是否为质数。 输出格式: 输出包含M行,每行为Yes或No,即依次为每一询问的结果。 ...
  • 一行包含两正整数N、M,分别表示查询的范围和查询的个数。 接下来M行每行包含一不小于1且不大于N的整数,即询问该数是否为质数。 Output 输出包含M行,每行为Yes或No,即依次为每一询问的结果。 Sample ...
  • 一行包含两正整数N、M,分别表示查询的范围和查询的个数。 接下来M行每行包含一不小于1且不大于N的整数,即询问概数是否为质数。 输出格式: 输出包含M行,每行为Yes或No,即依次为每一询问的结果...
  • 一行包含两正整数N、M,分别表示查询的范围和查询的个数。 接下来M行每行包含一不小于1且不大于N的整数,即询问概数是否为质数。 输出格式: 输出包含M行,每行为Yes或No,即依次为每一询问的结果。 ...
  • 一行包含两正整数N、M,分别表示查询的范围和查询的个数。 接下来M行每行包含一不小于1且不大于N的整数,即询问该数是否为质数。 输出格式 输出包含M行,每行为Yes或No,即依次为每一询问的结果。 ...

空空如也

空空如也

1 2 3 4 5
收藏数 100
精华内容 40
关键字:

查询第n个质数