競技プログラミングの解答がTLEになってしまう

Question

前提・実現したいこと

ご覧いただきありがとうございます。
実行時間制限で解けなかった問題でどうしても解法が気になってしまったので、質問さしていただきます。

・10^18以下の数字l,r(l<r)が与えられており
・m個のばらばらの数字n1,n2...nmが与えられている
(n<10^8である)

この時l~rの数字の中で、
n1の倍数でもなく
n2の倍数でもなく
...
nmの倍数でもない
数字は何個あるでしょうか？

という問題です。

以下は自分が書いたコードです。

#include <bits/stdc++.h>
using namespace std;

int main() {
  long long l,r;

  cin >> l >> r;
  long long numbers_number=r-l+1;
  vector<bool> numbers(numbers_number);
  fill(numbers.begin(), numbers.end(),true);

  int m;
  cin >> m;
  vector<int> n(m);
  for(int i=0; i<m ;i++){
    cin >> n.at(i);
  }

  for(int i=0; i<m ;i++){
    int N = n.at(i);
    int j;
    if(l%N){
      j=l/N+1;
    } else
    {
      j=l/N;
    }
    while (true)
    {
      numbers.at(j*N-l)=false;
      j++;
      if(N*j>r)break;
    }
  }

  long long result=0;
  for(int i=0; i<numbers_number; i++){
    if(numbers.at(i)==true){
      result++;
    }
  }

  cout << result;
}

発生している問題・エラーメッセージ

この解法ですと、
・l~rの幅が広い場合
→bad_allocとなり配列が宣言できない
要素数が少ない場合だと大丈夫ですが、
要素数1000000000000ぐらいから作成できなくなりました。
・複雑な場合だと制限時間で答えられない

のでTLEになってしまいました。

どのようにすれば、制限時間内に解けるのでしょうか？
よろしければご教授頂きたいです。

---

補足
実行時間制限は2秒でしたが、この解法ではtimeout(7秒以上)でした

すみません制約が一つ抜けていました。
m個は10以下です。

Comments

[SHOMI]

問題文へのリンクを貼っていただけますか？
>要素数1000000000000ぐらいから作成できなくなりました。
vector<bool>だけでメモリを116.4GBも要求していますよ…

Answer 1

包除原理を使うのがベターでしょうか。
l~rの範囲で、「いずれかの倍数である数」の個数を数え、全体から引きます。

Comments

[shugo]

回答ありがとうございました。
確かに倍数を考えて、全体の数より倍数の数を減らすやり方で解けそうでした。
Nが1の場合は、例外処理を加えれば大丈夫でした。

他の方もありがとうございました。

[swordone]

Nとは？

[shugo]

質問文を見直すと説明が不足していました。
すみません、問題文の中に
n1,n2...の中で一つが1で与えられた場合は、
例外的に全ての数を倍数として数えるとありました。

その場合の例外処理の話でした。

[swordone]

別に例外にする必要はないのでは？
1があった時点で答え0で確定して終了ならともかく。

[shugo]

重複の確認の為に今まで出てきた倍数を記憶したのですが、

1の場合のみ
10^18個の領域が必要になるので、例外処理が必要でした。
2の以上は、領域が確保出来たので大丈夫でした。

Answer 2

回答ではなく完全に独り言ですが…
10^8は領域確保できて、10^8回ループも時間内に回せますよね。
逆から考えるといけそうかな、と。
l～rの(r-l+1)個の数からすべての条件を満たさないものを引いていく感じ？