Hướng giải bài về số nguyên tố

[myhanh (Bảo Ngân)]

Mọi người cho em hỏi hướng giải của bài này với ạ:

Bài làm của em là như thế này ạ,nhưng chỉ đúng được 60% test thôi ạ:

include <bits/stdc++.h>
using namespace std;
long long i,j,a[100000001],max1,d[100000001],n,x[1000001],m,s,l,r;
void sang()
{
    for (i=2;i<=max1;i++) a[i]=1; a[1]=0;
    i=2;
    while (i<=sqrt(max1))
    {
        if (a[i]) for (j=2;j<=max1/i;j++) a[i*j]=0;
        i++;
    }
    for (j=2;j<=max1;j++)
        if (a[j]) for (i=1;i<=n;i++) if (x[i]%j==0) d[j]++;
}
int main()
{
    //freopen("SNT.inp","r",stdin);
    //freopen("SNT.out","w",stdout);
    cin>>n;
    for (i=1;i<=n;i++) {cin>>x[i]; max1=max(max1,x[i]);}
    cin>>m;
    sang();
    for (i=1;i<=m;i++)
    {
        s=0;
        cin>>l>>r;
        for (j=l;j<=r;j++) s+=d[j];
        cout<<s<<endl;
    }
}

Em cảm ơn ạ.

[noname00 (HK boy)]

Bạn không thể khai báo 2 cái mảng đến 10^8 phần tử như vậy được bị memory limit exceeded ngay lập tức.

Bạn để ý khoảng giá trị của x[] và l_i, r_i cách xa nhau như vậy, tận dụng sàng nguyên tố và tính chất về ước của số nguyên tố thì mỗi query có thể giảm kha khá bước tính toán.

Bạn tham khảo:

https://codeforces.com/blog/entry/22229

[rogp10]

Phần query thì bạn sử dụng prefix sum và “sparse array”
Phần setup mới là khó nhằn Làm sao mà lưu được 1 đống thứ trong 1 slot đây??? Thực ra bạn có thể “theo vết”, từ đây phân tích thừa số hàng loạt là khả dĩ.

[Grevyalres_X (Pzanitor)]

Đây là một bài trên codeforces
https://codeforces.com/contest/385/problem/C

Ý tưởng là dùng sàng nguyên tố để phân tích mỗi số ra thừa số nguyên tố.
Code: https://pastebin.com/A4sVpc7T

[myhanh (Bảo Ngân)]

Em cảm ơn ạ.
Em đã sửa lại bài được nhờ hướng dẫn của mọi người.

[rogp10]

var tricky = Array.prototype;
tricky.prefix_sum_sparse = function(key) { 
  var sum = 0;
  return this.reduce((x,y) => x.push([y, sum+=key(y)]), []);
}
tricky.lower_bound = function(x, k, g) {
   var rs;
   var l = 0, r = this.length;
   while(l < r) {
      var m = (l+r) >> 1;
      var t = k(this[m]);
      if(t == x) return g(this);
      else if(t > x) r = m;
      else rs = l = m;
   }
   return g(this[rs]);
}

var largest_prime_factor_sieve = function(n) {
   // a bit optimized
   var sieve = new Int32Array((n+1)>>1);
   var size = sieve.size;
   // để ý cận mở hơn bt, như vậy dễ code hơn và không cần chia gì cả.
   for(var i=1; i<=size; ++i) {
     if(sieve[i] !== 0) continue;
     for(var j=i+i; j<=size; j+=i) sieve[j] = j<<1+1;
   }
   return sieve;
}
var prep = function(numbers) {
   var largest_factors = largest_prime_factor_sieve(Math.max(...numbers));
   var l = function(o, kay) { o[kay]? ++o[kay] : o[kay] = 1; }
   var factors_cnt = numbers.reduce((x,y) => {
      while(y&1 === 0) { l(x,2); y >>= 1; }
      let t = 0;
      while((t = largest_factors[y>>1]) !== 0) {
          l(x, t); y/=t;
      }
      l(x,y<<1+1); return x; }, {});
   return Object.keys(factors_cnt).map(parseInt).prefix_sum_sparse(v => o[v]);
}

var solve = function(numbers, queries) {
   var preArray = prep(numbers);
   queries.forEach(v => console.log(preArray.upper_bound(v[1], v => v[0], v => v[1])
- preArray.lower_bound(v[0], v => v[0], v => v[1]));
}