Số X

Xem PDF

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

Thấy Khoa rất thích học toán, một hôm thầy giáo đã ra một bài toán cho Khoa giải như sau:

Xác định hai hàm \(f,g\) trên các số nguyên dương như sau:

  • \(f(n)\) = tích các chữ số khác 0 của \(n\)
  • \(g(n)\) có trị trị là:
    • \(n\) nếu n<10
    • \(g(f(n))\) ngược lại
      Khoa cần xử lý \(Q\) truy vấn, trong mỗi truy vấn sẽ được cung cấp 3 số nguyên \(l,r,k\). Khoa cần in số lượng số nguyên \(x\) nằm giữa \(l\)\(r\), trong đó \(g(x)=k\).

Input

  • Dòng đầu tiên chứa số nguyên \(Q\) \((1 \le Q \le 2 \times 10^5)\) đại diện cho số lượng truy vấn
  • \(Q\) dòng tiếp theo, mỗi dòng chứa 3 số nguyên \(l,r,k (1 \le l \le r \le 10^6,1 \le k \le9)\)

Output

  • Với mỗi truy vấn, in ra một dòng chứa câu trả lời cho truy vấn đó.

Example

Test 1

Input
4
22 73 9
45 64 6
47 55 7
2 62 4 
Output
1
4
0
8
Note
  • Có 1 số \(x\) để \(g(x)\)=9 đó là \(g(33)\)=9 với \(g(33)\)=\(g(3\times3)\)=\(g(9)\)=9
  • Có 4 số \(x\) để \(g(x)\)=6 là: \(g(47)\)=\(g(48)\)=\(g(60)\)=\(g(61)\)=6
  • Không có số \(x\) nào trong khoảng 47 đến 55 để \(g(x)\)=7.
  • Có 8 số \(x\) để \(g(x)\)=4 là: \(g(4)\)=\(g(14)\)=\(g(22)\)=\(g(27)\)=\(g(39)\)=\(g(40)\)=\(g(41)\)=\(g(58)\)=4

Bình luận

  • anhhaisaygex 9:50 a.m. 23 Tháng 12, 2024 chỉnh sửa 7
    #include <bits/stdc++.h>
    #define ll long long
    #define endl '\n'
    #define hien ios_base::sync_with_stdio(false); cin.tie(nullptr);
    #define taiz cout.tie(nullptr)
    #define saygex main()
    using namespace std;
    
    const ll nmax = 1e6 + 8;
    const ll mod = 1e9 + 7;
    const ll oo = 1e18;
    ll dp[nmax], q, mark[nmax][10];
    ll kq( ll n){
        while(true){
            ll res = 1;
            while(n > 0){
                if ( n % 10 != 0) res *= n % 10;
                n /= 10;
            }
            if ( res < 10) return res;
            n = res;
        }
    }
    void tao(){
        for ( ll i = 1; i <= 1e6; ++i){
            dp[i] = kq(i);
        }
    }
    void ktao(){
    
        for ( ll i = 1; i <= 1e6; ++i){
            for ( ll j = 1; j <= 9; ++j){
                mark[i][j] = mark[i - 1][j];
            }
            mark[i][dp[i]]++;
        }
    }
    saygex{
        hien taiz;
        tao();
        ktao();
        cin >> q;
        while(q--){
            ll l, r, x;
            cin >> l >> r >> x;
            cout << mark[r][x] - mark[l - 1][x] << endl;
        }
    
    }
    
    • penistone 2:02 p.m. 8 Tháng 1, 2024

      C++

      #include<bits/stdc++.h>
      #define int long long
      #define endl "\n"
      using namespace std;
      int F[10][1000001]={};
      int f(int n)
      {
          int d=1;
          while (n>0)
          {
              if (n%10!=0) d=d*(n%10);
              n=n/10;
          }
          return d;
      }
      int g(int n)
      {
          if (n<10) return n; else return g(f(n));
      }
      signed main()
      {
          ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
          int n,i,x,j,l,r;
          for(i=1;i<=1000000;i++)
          {
              x=g(i); F[x][i]=F[x][i-1]+1;
              for(j=1;j<=9;j++) {if (j!=x) F[j][i]=F[j][i-1];}
          }
          cin>>n; while (n--)
          {
              cin>>l>>r>>x; cout<<F[x][r]-F[x][l-1]<<endl;
          }
          return 0;
      }
      

      • rukashii 9:34 p.m. 30 Tháng 12, 2021

        Bình luận bị ẩn vì nhiều phản hồi tiêu cực. Nhấp vào đây để mở.