Số đặc biệt (TS10 LQĐ, Đà Nẵng 2021)

Xem PDF

Tất cả bài nộp

Các bài nộp tốt nhất

Thời gian:

Python 3 6.0s

Bộ nhớ:

Python 3 500M

Tác giả:

Small

Dạng bài

Điểm: 100 (p) Thời gian: 1.0s Bộ nhớ: 640M Input: bàn phím Output: màn hình

Hiếu rất yêu thích số nguyên tố, đồng thời cùng rất yêu thích số \(5\). Hiếu luôn coi các số nguyên tố có tổng các chừ số chia hết cho \(5\) là số đặc biệt. Lần này, thầy giáo đưa cho Hiếu \(2\) số nguyên dương \(L, R\). Hiếu muốn biết trong đoạn \([L, R]\) có bao nhiêu số đặc biệt nên nhờ các bạn trả lời giúp.

Input

Dòng đầu tiên chứa số nguyên dương \(T\) \((1 \leq T \leq 100)\) là số lượng thử nghiệm.
\(T\) dòng tiếp theo, mỗi dòng chứa hai số nguyên dương \(L\) và \(R\) \((0 < L \leq R \leq 3 \times 10^{6})\) theo thứ tự, phân tách nhau bởi dấu cách.

Output

Ghi ra \(T\) dòng, dòng thứ \(i\) ghi một số là số lượng số đặc biệt trong đoạn \([L,R]\) thứ \(i\) tương ứng theo thứ tự trong đầu vào.

Example

Test 1

Input

2
1 10
4 20

Output

1
2

Note

Giải thích:

Trong đoạn \([1, 10]\) có \(1\) sô đặc biệt là \(5\).
Trong đoạn \([4, 20]\) có \(2\) số đặc biệt là \(5\) và \(19\) \((1 + 9 = 10)\).

Bình luận

penistone • 3:17 p.m. 31 Tháng 1, 2024 •

Hint

Prefix-sum + Sieve

0
Phản hồi Chia sẻ

My_hint

Sieve tối ưu + kiểm tra tính chia hết cho 5 trâu bò

Code

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

const ll N = 3 * 1e6;
ll arr[N], L, R, res, t;

void snt() {
  arr[1] = 1;
  arr[0] = 1;
  for(ll i = 4; i <= N; i += 2) arr[i] = 1;
  for(ll i = 3; i*i <= N; i += 2) {
    for(ll j = i; j*i <= N; j += 2) arr[i*j] = 1;
  }
}

bool check(ll x) {
  ll a = 0;
  while (x > 0) {
    a += x % 10;
    x = x / 10;
  }
  if (a % 5 == 0) return true;
  return false;
}

int main() {
  snt();
  cin >> t;
  while(t--) {
    res = 0;
    cin >> L >> R;
    for(ll i = L; i <= R; i++) {
      if(arr[i] == 0 and check(i) == true) res++;
    }
    cout << res << "\n";
  }
  return 0;
}

Phản hồi

1 bình luận nữa