记录编号	588830	评测结果	AAAAAAAAEEEEEEEEEEEE
题目名称	水母序列	最终得分	40
用户昵称	liuyiche	是否通过	未通过
代码语言	C++	运行时间	5.512 s
提交时间	2024-07-01 15:26:39	内存使用	18.12 MiB

        #include <bits/stdc++.h>
                        
        using namespace std;
         
        int n, m;
        int a[100005];
        int f[1005][1005];
        int v[2097165];
         
        inline void Isprime()
        {
            v[1] = 2;
            v[0] = 2;
            for (int i = 2; i <= 2097160; ++i)
            {
                if (v[i] == 0)
                {
                    for (int j = i; j <= 2097160/i; ++j)
                        v[i*j] = 2;
                }
            }
        }
                
        int main()
        {
            freopen("Jelly.in", "r", stdin);
            freopen("Jelly.out", "w", stdout);
                    
            ios::sync_with_stdio(false);
            cin.tie(0); cout.tie(0);
            
            Isprime();    
            cin >> n >> m;
            for(int i = 1; i <= n; ++i)
                cin >> a[i];
            for(int i = 1; i <= n; ++i)
                if(v[a[i]] == 0)
                    f[i][i] = 1;
            for(int i = 1; i <= n; ++i)
                for(int j = i+1; j <= n; ++j)
                {
                    f[i][j] = f[i][j-1]+f[j][j];
                    int tmp = a[j];
                    for(int k = j-1; k >= i; --k)
                    {
                        tmp |= a[k];   
                        if(v[tmp] == 0)
                            f[i][j]++;
                    }
                }
            
            for(int i = 1; i <= m; ++i)
            {
                int l, r;
                cin >> l >> r;
                cout << f[l][r] << '\n';
            }
                
           	return 0;
        }